Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A variable $A$ in a context free grammar $G= \langle V, \Sigma, S, P\rangle$ is live if $A \Rightarrow^* x$ for some $x \in \Sigma^*$. Give a recursive algorithm for finding all live variables in a certain context free grammar.

I don't necessarily need an answer to this. Mostly I am having a very difficult time deciphering what this question is asking. More specifically its definition of live variables.

share|improve this question
Pretend that $A$ is the initial symbol: starting from it, can you generate some word consisting entirely of terminal symbols? If so, $A$ is live. –  Brian M. Scott May 16 '12 at 9:00
@BrianM.Scott So isn't that every variable? Unless A->C and C->xC in which case it would be infinite? –  canton May 16 '12 at 9:08
It’s possible that every non-terminal is live, but it’s also possible to have non-terminals that aren’t live. The exercise is to find a ‘nice’ way to find the live ones, given only the grammar. It isn’t always obvious whether a non-terminal is live or not. –  Brian M. Scott May 16 '12 at 9:10
Okay, now I understand the definition of 'live' and am still stumped. –  canton May 16 '12 at 9:20
Hint: A terminal can be shown to be live if a) it is the LHS of a rule whose RHs consists only of terminals or b) it is the LHS of a rule whose RHS consists only of terminals and safe non-terminals. This yields a simple iterative algorithm: start by finding a set of non-terminals satisfying a), and enlarge using b) until no more changes occur. Transform this into a recursive algorithm and you are done. –  Johannes Kloos May 16 '12 at 9:28

1 Answer 1

Consider this example:

S → A | B
A → aA | a
B → bB
C → c

This is a grammar for the set of all nonempty strings of a.

The symbol B is not live, because it is never involved in the production of a terminal string; you can generate it from S or from B, but you can never finish the production because you can never get rid of it. So productions involving B are useless, and you can delete from the grammar them without changing the language that is generated:

S → A
A → aA | a
C → c

Another way that a symbol might fail to be live is if there is no way to produce it from the start symbol. C is an example here, and again, productions involving C can be deleted from the grammar without changing the language:

S → A
A → aA | a

Your job is to describe an algorithm that decides which of the symbols in a grammar are live.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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