I have the following grammar for a context-free language:

$G = (\{S,A,B\}, \{x,y,z\}, P, S)$ with $P = \{S \rightarrow A, A \rightarrow xAz, A \rightarrow xBz, B \rightarrow y\}$

My question is: How to construct a pushdown automaton associated with the above grammar?

  • $\begingroup$ Automata is a plural. The singular is automaton. I cannot answer you because I do not know what definition of PDA you are using. In what case does it accept? (there are several ways to define that). $\endgroup$ – babou Jan 4 '15 at 0:55
  • $\begingroup$ @babou the one that accepts words when it is empty. $\endgroup$ – Highlights Factory Jan 4 '15 at 9:33
  • $\begingroup$ What have you tried? Have you read an automata theory textbook? This is covered in standard automata theory textbooks, where they prove that a language can be accepted by a pushdown automaton iff it is context-free. We expect you to do a significant amount of research before asking, and to show us in the question what research you've done. If you haven't already consulted standard resources, there's little point in us repeating standard material that's already found in existing textbooks. $\endgroup$ – D.W. Jan 5 '15 at 1:05
  • 1
    $\begingroup$ Your question is ambiguous, in a way. Are you seeking help to solve this specific problem, in which case you are indeed better off analysing the structure of this very simple language and using the understanding to imagine a PDA (which is what the answers are giving you), or are you trying to learn how to do it in general, which is a different matter (though the answer should be available in any textbook)? In the latter case, these answers will teach you very little. $\endgroup$ – babou Jan 5 '15 at 10:12

The language $L$ accepted by the CFG can be written of the form,

$$ L = \{x^nyz^n | n \gt 0\}$$

You can verify this, by looking at members of $L$

Now there are various definitions of $PDA$ (accept by final state, accept by empty stack), the most simple definition that is suitable for this problem is to user a $PDA$ that accepts through empty stack.

Now the intuitive idea is to push all $x$'s on to the stack, and when you read a $y$, pop the $x$'s in the stack for every $z$ you read afterwards. (So this can be quite easily achieved by a deterministic $PDA$. Verify.)

The transition table $T$ for a $PDA$, with states $Q = \{q_0, q_1,q_2,q_3\}$ and stack symbols $\{X,\$ \}$ is:

$$ \delta (q_0,$,x) = (q_1,$X) $$ $$ \delta (q_1,\epsilon,x) = (q_1,X) $$ $$ \delta (q_1,\epsilon,y) = (q_2,\epsilon) $$ $$ \delta (q_2,X,z) = (q_2,\epsilon) $$ $$ \delta (q_2,$,\epsilon) = (q_3,\epsilon) $$

The automaton transitions to state $q_3$ once an equal number of $x$'s and $z$'s are read

NOTE: My first answer. Kindly bear with errors (technical or LaTex related)

  • $\begingroup$ tnx for the answer, but could you explain stack symbols {X,Y,}$? What does $ mean, is it the lowest stack symbol(= #)? Why you use X,Y and leave A,B are they the same or not? Also I think there is a small error in you LaTeX code stack symbols {X,Y,}$ (not escaped $). $\endgroup$ – Highlights Factory Jan 4 '15 at 11:54
  • $\begingroup$ Also what happens when I read an y? For x and z is clear to me - when read x, push X, when read z, pop X. $\endgroup$ – Highlights Factory Jan 4 '15 at 12:04
  • $\begingroup$ (1) $\$$ is used to denote an empty stack (you can use $#$ as well), it is, as you say, the lower most symbol on the stack (2) Stack symbols could be anything it doesn't matter if they are $A,B$ or anything else, as long as they are properly defined in the transition table. (3) Once a $y$ is read, the automaton changes to a different state ($q_2$) and no change is made to the stack, this is performed when at $q_1$ you read a $y$ in the input, the transition to $q_2$ is made $\endgroup$ – Vigneshwaren Jan 4 '15 at 13:34
  • $\begingroup$ Must $q_3$ be defined in Q at the beginning of the table, because it is used in it? $\endgroup$ – Highlights Factory Jan 4 '15 at 17:34
  • $\begingroup$ Lastly, why is Y defined in the Stack symbols and not used later in the table? $\endgroup$ – Highlights Factory Jan 4 '15 at 17:42

Keep pushing every x you read. When a y is read, then start reading z's. For every z you read pop an x. If the letter read is lamda and the letter popped is also lambda, go to accept state, otherwise if letter read is lambda and letter popped is not lambda or vice versa go to reject state.

  • $\begingroup$ When a y is read, then start reading z's. How to implement this? $\endgroup$ – Highlights Factory Jan 4 '15 at 12:07
  • $\begingroup$ Read y. Read z. Pop x. Read z. Pop x, and so on. If lambda is read and lambda is popped then go to accept state, else if lambda is read but stack is not empty then go to reject state else if z is read but lambda is popped from stack then go to reject state. $\endgroup$ – user4129542 Jan 5 '15 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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