0

How can I draw the pushdown automaton for the language $\{w \in \{a,b,c\}^{*}:w \text{ is of the form } y c y^{R}, y \in \{a,b\}^{*}\}$?

evinda
  • 7,823

2 Answers2

1
  • let's call the starting state COPY
  • on input character $a$ or $b$, PUSH this into the stack and stay on state COPY
  • if character $c$ is the input, move to state CHECK
  • from state CHECK, input $c$ leads to state ERROR
  • similarly, both cases (tape: $a$, POP: $b$), $\ $(tape: $b$, POP $a$) lead to state ERROR
  • the other two inputs (tape: $a$, POP: $a$), $\ $(tape: $b$, POP $b$) stay on state CHECK
  • finally (tape: EOT, POP: empty) goes to state ACCEPT
Berci
  • 90,745
1

That's what I have tried.Do you mean that I should do something like that?

enter image description here

evinda
  • 7,823
  • 1
    Yes, something like that. I don't exactly know how a stack (pushdown) automaton is pictured usually, I mean how to indicate the PUSH/POP informations and how to distinguish the stack input (POP) from the tape input in the drawing... – Berci Dec 31 '13 at 12:43
  • If I want to show that a language is accepted by a pushdown automaton,do I have to draw one or could I just write something like that,what you have written in your previous post? – evinda Dec 31 '13 at 12:53
  • 1
    if you write it down, it's usually clearer. If the exercise was specifically to draw, then add some picture.. – Berci Dec 31 '13 at 14:17