# Math Help - context-free grammar

1. ## context-free grammar

Hi,
I need some help with this.
Can you explain me the part 'Identifying useless variables' at the page 8 on some simple example?
Thank you.

silapo.72@gmail.com

I need to explain how to use alogorithm pre* at grammar reduction. Can you explain me it on some example please?

The problem is described in link down:
http://www7.in.tum.de/um/bibdb/esparza/ufpcfg.pdf

2. I need to explain how to use alogorithm pre* at grammar reduction. Can you explain me it on some example please?
pre* is not an algorithm, but an operator that maps a language into a language. The description of how the operator actually works depends on how the input and output languages are represented. The article assumes that they are represented by finite automata, so it gives an algorithm that takes an automaton accepting the input language and produces an automaton accepting the output language.

So, do you need an explanation how the automata-converting algorithm works or how it is used for the task of finding useless variables? For the second, consider the following grammar.

S -> AB
A -> a | aA
B -> BA

Here B is useless because it is not productive, i.e., it is not the case that $B\stackrel{*}{\Rightarrow} w$ for some $w\in T^*=\{a\}^*$. To come to this conclusion using the suggested method, we start with an automaton M1 that accepts all of $\{a\}^*$. It consists of one accepting state with a loop labeled by $a$. The algorithm described in the article transforms this automaton into an M2 such that M2 accepts $u\in\{S,A,B,a\}^*$ iff $u\stackrel{*}{\Rightarrow}w$ for some $w\in\{a\}^*$. Then we check whether M2 accepts B (it should not).

The variable A is productive; however, it is also useless because it is not reachable, i.e., it is not the case that $S\stackrel{*}{\Rightarrow}w_1Aw_2$ for some $w_1,w_2\in\{a\}^*$. This is because every string obtained from S (the article calls them sentential forms) has a B in it. To come to this conclusion, we start with an automaton N1 that accepts the language $a^*Aa^*$. (To be precise, this is a regular expression that describes the language.) The algorithm converts it into an N2 that accepts $u\in\{S,A,B,a\}^*$ iff $u\stackrel{*}{\Rightarrow}w$ for some $w\in a^*Aa^*$. Then we check whether N2 accepts S (it should not).

3. Thanks for replie.
You asked me, what I need to explain, so I need an explanation how it is used for the task of finding useless variables on some simple example.