Теория автоматов: преобразование контекстно-свободной грамматики в DFA

Как преобразовать контекстно-свободную грамматику в DFA? Это легко сделать, если у нас есть переходы типа A->a B. Но когда у нас есть переходы типа A->a B c. Тогда как мы должны представить его как DFA


dfa finite-automata
person bulbasaur    schedule 30.03.2014    source источник
comment
Вы не всегда можете преобразовать CFG в DFA, но да, если это леволинейный или правый лайнер, вы можете. В этом случае этот ответ может быть полезен Левая и правая линейная грамматика   -  person Grijesh Chauhan    schedule 30.03.2014
comment
и поэтому для A-›a B c мы не можем построить dfa??   -  person bulbasaur    schedule 30.03.2014
comment
Посмотрите, как правильно сначала преобразовать грамматику в левый или правый лайнер, а затем нарисовать DFA. Если невозможно преобразовать CFG в леволинейный (правый лайнер), то на самом деле грамматика генерирует CFL, который является надмножеством обычного языка, и DFA для CFL невозможен. A -> a B c Только одно производственное правило (не грамматика), поэтому ваш вопрос не имеет смысла   -  person Grijesh Chauhan    schedule 30.03.2014

Ответы (2)


arrow_upward
0
arrow_downward

Во-первых, вы должны преобразовать свой язык в CNF (нормальная форма Хомски). Затем шаги для преобразования таковы:

  1. Преобразование его в левую/правую грамматику называется обычной грамматикой.

  2. Преобразование обычной грамматики в конечные автоматы Переходы для автоматов получаются следующим образом. каждая продукция A -> aB делает δ (A, a) = B, то есть make an, помечена буквой «a» от A до B. Для каждой продукции A -> a make δ (A, a) = конечное состояние. Для каждой продукции A -> ϵ сделайте δ (A, ϵ) = A, и A будет конечным состоянием.

person e nahang    schedule 14.06.2015
comment
Эта процедура не всегда будет работать — она может завершиться ошибкой, потому что CFG предназначена для нерегулярного языка или потому, что преобразование в CNF дает нелинейную слева или нелинейную справа грамматику. - person templatetypedef; 26.06.2021

arrow_upward
0
arrow_downward

Не существует общей процедуры для преобразования произвольной CFG в DFA. Например, рассмотрим эту CFG:

S → aSb | ε

Эта грамматика предназначена для языка { anbn | n ≥ 0 }, который является каноническим нерегулярным языком. Поскольку мы можем создавать DFA только для обычных языков, нет возможности создать DFA с тем же языком, что и эта CFG.

person templatetypedef    schedule 26.06.2021