У меня есть эта грамматика
S->aSbA S->e A->aB B->bAпроверки, если регулярный язык приведена CF грамматика
Как я могу определить, является ли язык регулярно? Моя проблема в том, что у A и B нет терминального символа, поэтому я не знаю, какие языки он будет производить.
Для этого не существует общего метода. Регулярность - неразрешимая проблема для контекстно-свободных языков.
В вашем конкретном случае, как указал J Earls, единственным словом, которое вы можете получить, является пустое слово. Все деривации, которые используют правило, отличное от S -> e, никогда не заканчиваются. Таким образом, язык является конечным и поэтому регулярным.
Возможно, вы захотите попробовать этот вопрос на сайте [computer science stackexchange] (http://cs.stackexchange.com/). –
'e' - пустое слово, не так ли? –
Этот язык даже не заканчивается. Никогда не бывает условий, в которых вы не ищете другого символа. –