19
$\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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Not quite: proper CFGs must meet two more requirements. So I'd reformulate this. $\endgroup$
    – reinierpost
    Jan 24, 2017 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, 2017 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, 2017 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, 2017 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, 2017 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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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