что имеется в виду под контекстом бесплатно не регулярно

Question

Я готовлю контекстную грамматику к экзамену. Я не мог понять, почему язык

{ a^n b^n | n>=0}

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

Спасибо

Answer 1

Выражение не является регулярным, если оно не может (точно) соответствовать регулярному выражению или (эквивалентно) конечному автомату . См. Также контекстно-свободный язык и обычный язык .

Answer 2

Стандартный подход заключается в использовании Pumping Lemma

Answer 3

Как сказано в предыдущих ответах, его контекст не зависит от контекста, так как вы можете выразить его с помощью контекстно-свободной грамматики.

Например: S -> aSb | ε

Это не регулярно, потому что вы не можете выразить это с помощью конечного автомата или регулярных выражений. Вы должны быть в состоянии посчитать количество As и проверить, совпадает ли количество Bs. Это не может быть сделано с конечными состояниями, так как n может быть чем угодно

Answer 4

Ну, вы можете сказать, что это не зависит от контекста, потому что вы можете выразить это с помощью контекстно-свободной грамматики. Однако оно не является регулярным, поскольку регулярное выражение (и конечные автоматы) не может представлять этот язык.