1
$\begingroup$

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.

  • 0
    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.2012-05-16
  • 0
    @BrianM.Scott So isn't that every variable? Unless A->C and C->xC in which case it would be infinite?2012-05-16
  • 1
    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.2012-05-16
  • 0
    Okay, now I understand the definition of 'live' and am still stumped.2012-05-16
  • 2
    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.2012-05-16

2 Answers 2