Можно ли преобразовать все контекстные свободные грамматики в NFA/DFA?

Question

Я видел это сообщение о том, как преобразовать бесконтекстный грамматик ДКУ: Automata theory : Conversion of a Context free grammar to a DFA

Однако, просто интересно, могут все контекстные свободные грамматики быть преобразованы в DFA/NFA? Что относительно контекстных свободных грамматик, которые не могут быть выражены как регулярное выражение? Ex. S -> (S) |()

Спасибо!

Answer 1

Только обычные языки могут быть преобразованы в DFA, и не все CFG представляют собой обычные языки, в том числе и в вопросе.

Таким образом, ответ «нет».

NFAS не более выразительный, чем ДКА, поэтому приведенное выше утверждение будет по-прежнему верно, если вы заменили DFA с NFA

CFG представляет собой регулярный язык, если он является правым или левым линейно. Но тот факт, что CFG не левый или правый-линейный, ничего не доказывает. Например, S→a | a S a происходит с тем же языком, что и S→a | S a a.