Как я могу видеть, что язык не является регулярным

Question

L = {a^n b^n c^n}, как я могу сказать прямо, не глядя на производственные правила, что этот язык не является регулярным? я могу использовать лемму накачки, но некоторые ребята говорят, что просто смотрят на грамматику, что это не обычная. как это возможно?

Answer 1

У вас есть три символа в вашем алфавите. Все они зависят от одной и той же переменной: n. Теперь, если у вас есть только два из них, представьте {a^n b^n}, вы можете легко выполнить задачу с этой продукцией:

S -> ab | aSb

Но у вас их три, и нет возможности связать их все с одной и той же переменной. Вы должны использовать две категории синтаксиса, но, поскольку вы это делаете, они не связаны друг с другом, и вы можете создавать разные строки из каждого из них. Единственный способ связать их - это только одна категория синтаксиса, и это невозможно.

Вы не можете сделать:

S -> ABC | aSbc

На самом деле вы не можете иметь категорию синтаксиса в своей последней строке, так что это не строка. Его нужно снова преобразовать. И что вы можете сделать с этого момента? Вы можете сделать:

aabcbc

или вы можете сделать:

aaSbcbc

Первая строка, а не является частью вашего языка. Во-вторых, это еще не строка. Но очень легко понять, что вам не удастся сделать какую-либо разрешенную строку.