Czy mogą istnieć „martwe stany” w gramatyce bezkontekstowej?

Czy gramatyka bezkontekstowa może zawierać „martwe stany” z automatu, np

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)\,?$

$B\to C$ $C\to cC$ will loop forever and never generate a word. Is this allowed or MUST production rules end with an terminal at some point?

context-free automata formal-grammars r3r57
źródło

Odpowiedzi:

Context-free grammars are allowed to contain unproductive rules. This is accepted, because every CFG generates the same language as some proper CFG which contains no unproductive rules, no empty string productions, and no cycles; so it is safe to assume that a CFG is proper without loss of generality.

ilke444
źródło

Not quite: proper CFGs must meet two more requirements. So I'd reformulate this.

reinierpost

@reinierpost: I guess you mean there exist classes of CFGs that forbid unproductive rules, but still include non-Proper CFGs? I guess the reformulation could be as simple as: "unless, for example, they are"

mhelvens

I mean not every CFG without unproductive rules is proper, which contradicts your statement; but the definition of proper CFGs, by explicitly excluding unproductive rules, makes it clear that these are possible in arbitrary CFGs, so that is what I'd write.

reinierpost

Thank you for your improvements. I meant to say that there are subclasses of CFGs that they are not allowed to contain such rules.

ilke444

Is there a proper CFG which contains no unproductive rules, no empty string productions, and no cycles which generates the same language as ({a}, {A}, {A->epsilon},A)? I like the first sentence. Maybe the second sentence should be "This is because the definition of CFGs allows any finite string of terminals and nonterminals as the left hand side of a production."

Theodore Norvell

Yes of course. Every NFA can be written as a CFG. And building a DFA with a 'dead state' (the term I was taught, is 'sink') is trivial.

Example:

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

$G = (\{a\}, \{A\}, \{A\to A\},A)$ is a CFG that describes the empty language over the alphabet

{a}

$\{a\}$ .

Analogous to the NFA with only one non-accepting starting state and only a self-transition with $\epsilon$ .

David
źródło