Peut-il y avoir des «états morts» dans une grammaire sans contexte?

Une grammaire sans contexte peut-elle inclure des "états morts" d'un automate, tels que

g = ({une, b, c}, {UNE, B, C}, {UNE \to une B, B \to b, B \to C, C \to c C}, UNE) ?

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

Les règles de production et boucleront pour toujours et ne généreront jamais un mot. Est-ce que cela est autorisé ou DOIT se terminer avec un terminal à un moment donné? $B\to C$ $C\to cC$

context-free automata formal-grammars r3r57
la source

Réponses:

Les grammaires sans contexte peuvent contenir des règles improductives . Ceci est accepté, car chaque CFG génère le même langage que certains CFG appropriés qui ne contiennent aucune règle improductive, aucune production de chaîne vide et aucun cycle; il est donc sûr de supposer qu'un CFG est approprié sans perte de généralité.

ilke444
la source

Pas tout à fait: les CFG appropriés doivent répondre à deux autres exigences. Je reformulerais donc cela.

reinierpost

@reinierpost: Je suppose que vous voulez dire qu'il existe des classes de CFG qui interdisent les règles improductives, mais qui incluent toujours des CFG non appropriés? Je suppose que la reformulation pourrait être aussi simple que: "à moins que, par exemple, ils le soient"

mhelvens

Je veux dire que chaque CFG sans règles improductives n'est pas approprié, ce qui contredit votre déclaration; mais la définition des CFG appropriés, en excluant explicitement les règles improductives, montre clairement que celles-ci sont possibles dans les CFG arbitraires, c'est donc ce que j'écrirais.

reinierpost

Merci pour vos améliorations. Je voulais dire qu'il existe des sous-classes de CFG qui ne sont pas autorisées à contenir de telles règles.

ilke444

Existe-t-il un CFG approprié qui ne contient aucune règle improductive, aucune production de chaîne vide et aucun cycle qui génère le même langage que ({a}, {A}, {A-> epsilon}, A)? J'aime la première phrase. Peut-être que la deuxième phrase devrait être "C'est parce que la définition des CFG autorise toute chaîne finie de terminaux et de terminaux non terminaux comme côté gauche d'une production."

Theodore Norvell

Oui bien sûr. Chaque NFA peut être écrit en CFG. Et construire un DFA avec un «état mort» (le terme qui m'a été enseigné est «couler») est trivial.

g = ({une}, {UNE}, {UNE \to UNE}, UNE)

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

{a}

$\{a\}$

$\epsilon$

David
la source