18
$\begingroup$

Can a context-free grammar include "dead states" from an automaton, such as

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

The production rules $B\to C$ and $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?

$\endgroup$
24
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Not quite: proper CFGs must meet two more requirements. So I'd reformulate this. $\endgroup$ – reinierpost Jan 24 '17 at 11:47
  • $\begingroup$ @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" $\endgroup$ – mhelvens Jan 24 '17 at 15:44
  • $\begingroup$ 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. $\endgroup$ – reinierpost Jan 24 '17 at 16:07
  • $\begingroup$ Thank you for your improvements. I meant to say that there are subclasses of CFGs that they are not allowed to contain such rules. $\endgroup$ – ilke444 Jan 24 '17 at 18:35
  • $\begingroup$ 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." $\endgroup$ – Theodore Norvell Jan 25 '17 at 0:21
3
$\begingroup$

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)$$ is a CFG that describes the empty language over the alphabet $\{a\}$.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.