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.

  • 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

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.

0
  1. Make a list of all the variables. Each variable will get a check mark next to it if it is live. Initially no variable has a check mark.
  2. Make a list of all the productions. Each production will be crossed out when it is used.
  3. Repeatedly scan the list of productions, ignoring the crossed-out ones. If a production has variable $V$ on the left-hand side, and if all the variables on the right-hand side already have check marks, then give $V$ a check mark also, and cross out all the productions with $V$ on the left-hand side. Note that "all the variables on the right-hand side" includes the case where there are no variables on the right-hand side.
  4. When you finish a scan of the list of productions without crossing any out, stop.

For example, suppose the productions are:

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

On the first scan of the productions, we see that $A$ and $C$ have productions $A → a$ and $C → c$ where all the variables on the right-hand side are checked. So we check $A$ and $C$ and cross off the productions for these variables. The remaining productions are now:

S → A
S → B
B → bB

Now we see that $S$ has the production $S → A$ where all the variables on the right-hand side are checked, so we check $S$ and cross off its productions, leaving only:

B → bB

We cannot add $B$ to the list of live variables, so we are finished; $A, C, $ and $S$ are live.