Pode haver 'estados mortos' em uma gramática livre de contexto?

18

Uma gramática livre de contexto pode incluir "estados mortos" de um autômato, como

G=({a,b,c},{A,B,C},{AaB,Bb,BC,CcC},A)?

As regras de produção e se sempre e nunca geram uma palavra. Isso é permitido ou DEVE as regras de produção terminarem com um terminal em algum momento?BCCcC

r3r57
fonte

Respostas:

24

Gramáticas isentas de contexto podem conter regras improdutivas . Isso é aceito, porque todo CFG gera o mesmo idioma que um CFG adequado, que não contém regras improdutivas, produções de strings vazias e ciclos; portanto, é seguro assumir que um CFG é adequado sem perda de generalidade.

ilke444
fonte
Não é bem assim: os CFGs adequados devem atender a mais dois requisitos. Então, eu reformularia isso.
reinierpost
@reinierpost: Eu acho que você quer dizer que existem classes de CFGs que proíbem regras improdutivas, mas ainda incluem CFGs não adequados? Eu acho que a reformulação pode ser tão simples como: "a menos que, por exemplo, eles são"
mhelvens
Quero dizer, nem todo CFG sem regras improdutivas é adequado, o que contradiz sua afirmação; mas a definição de CFGs adequados, excluindo explicitamente regras improdutivas, deixa claro que isso é possível em CFGs arbitrários, e é isso que eu escreveria.
reinierpost
Obrigado por suas melhorias. Eu quis dizer que existem subclasses de CFGs que eles não têm permissão para conter essas regras.
precisa saber é o seguinte
Existe um CFG adequado que não contenha regras improdutivas, produções de strings vazias e ciclos que gerem o mesmo idioma que ({a}, {A}, {A-> epsilon}, A)? Eu gosto da primeira frase. Talvez a segunda frase deva ser "Isso ocorre porque a definição de CFGs permite que qualquer cadeia finita de terminais e não terminais seja o lado esquerdo de uma produção".
Theodore Norvell
3

Sim, claro. Todo NFA pode ser escrito como um CFG. E construir um DFA com um 'estado morto' (o termo que me ensinaram é 'afundar') é trivial.

G=({uma},{UMA},{UMAUMA},UMA)
{uma}

ϵ

David
fonte