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

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

G = ({a, b, c}, {A, B, C}, {A \to a B, B \to b, B \to C, C \to c C}, A) ?

$G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,?$

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? $B\to C$ $C\to cC$

context-free automata formal-grammars r3r57
fonte

Respostas:

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

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}, {UMA \to UMA}, UMA)

$G = (\{a\}, \{A\}, \{A\to A\},A)$

{a}

$\{a\}$

$\epsilon$

David
fonte