computer science
I'm trying to understand how you derive a context free grammar (CFG) from a Pushdown Automata (PDA)?
I have the following PDA.
I believe the following context-free language can be derived..
{0^n1^n|n≥0}
My problem is I don't understand how you can build the context free grammar from a PDA and vice versa. How would I build a PDA from a CFG? I'd really appreciate if someone could walk me through this process.
Found the trick to finish the proof. We just need to increasing the size of the pump. Let $v$ be the number of variables in a Chompsky normal form grammar. If $2^v$ is the ordinary pumping length. Consider a new length $2^{3v}$. In the parse tree of a long string (of minimal length) of length greater than $2^{3v}$, there must be a path of height $3v$. Thus some variable must occur 3 times. Then use the minimality of the parse tree to conclude that the stepwise retiteration can be pumped.
ok lets consider a string x , we have 2 cases :
for ex , x = 1010 , x+1 = 1010 + 1 = 1011
so in this case , clearly y is the same as x , except for the last symbol
so , if the last symbol in x , that is the top of the stack after pushing all symbols of x , if it is 0 , we need to make sure that the first symbol in y^r (which is the last symbol in y ) is 1 , then we need to make sure all other symbols match x ,
for ex , x = 1011 , x+1 = 1011 + 1 = 1100 , what happened here ?
if the last symbol in x is 1 , then in y , starting from least significant bit (rightmost symbol) , all 1s become 0s , then the first 0 we encounter becomes a 1 , the rest of the string remains the same , this is due to adding 1 , then having the carry added and so on
so in case 2 , we make sure that all 1s in x are 0s in y , till we reach the first 0 in x , which is a 1 in y , then all symbols are the same
other cases :
when we reach the state same we expect both binary strings to be the same from this point on , but x or y may have different number of leading 0s
the leading 0s are found at beginning of y , thus at end of y^r , so if we reach the accept state , meaning y = x+1 , we allow reading as much 0s as we want since we know these are leading 0s that do not change the number
if x is the one with more leading 0s , then we guess non-deterministically that input has ended , and what remains on stack are all leading 0s , we head to the state x 0s where we pop all leading 0s then accept , of course in the process if we are face with a 1 , this means these 0s are not leading 0s and we reject
we mentioned how if y ends with a 1 , we need to check for the first 0 in x to change to 1 in y , but what if x has only 1s ? , ex x = 1 , y = 10 , we check that 1 has turned to 0 , then if we find no 0s , we will find the # , the # will tell us that the string ended , and thus when x = 1 , the stack is #1 but we treat the # as a leading 0 , then we push it back for the final check for empty string , so the original rule is 1,0,ε , the rule we add is 1,#,# , we pop the # instead of the 0 ,fair enough since we know this is the end of the string anyway so we can say that #1 is same as #01 , then we push the # again for the final test of emptiness of stack
Now here is the PDA :
Best Answer
To construct a PDA from CFG, we only need to use these two simple rules:
The first rule is simple and straightforward, but the second rule requires a little bit of work. Let says, we have a CFG defined as follows: $$S \rightarrow aTXb$$ $$T \rightarrow XTS | \epsilon$$ $$X \rightarrow a | b$$ Initially, we have three states, where S stands for starting rule and \$ stands for stack symbol. Your book probably uses Z for stack symbol, so feel free to change it. It's just the matter of preference.
The restriction of a stack in PDA is that we can only push "one" symbol at a time. So to push a production rule onto a stack, we will break them into variables and terminals. Specifically, have a look at above picture, you can see that the first transition rule says push $S\$$ onto a stack, where $\$$ is stack symbol. This is not allowed in PDA, so we have to break the transition into two steps:
Note that this transition is a little special because it involves both stack variable $\$$ and the starting variable $S$. The next example of breaking long production rule should be more obvious. Firstly, all the production rule will go through the state after we pop $S$, i.e 2. We then apply the same procedure for any production rule that has length greater 1. So our first transition graph is as below:
In this graph, here are three transitions that need to be reconstructed. They are: $$\epsilon, \epsilon \rightarrow S\$$$ $$\epsilon, S \rightarrow XTS$$ $$\epsilon, S \rightarrow aTXb$$
Since we've already done $\epsilon, \epsilon \rightarrow S$, the next transition need to reconstructed is $\epsilon, S \rightarrow aTXb$. Note that the order of popping is from "right to left". So we pop $S \rightarrow T \rightarrow X$ respectively as below:
Reconstruct the last transition rule $\epsilon, S \rightarrow aTXb$, we have our final PDA as follows:
Reference