2

I am new to PDA, teacher is using different format, I see different notation for transition function I am not able understand teacher's format in this question for transition function of PDA!

Problem $\mathbf {611}\quad$ Let $L$ be the language accepted by the pushdown automaton: $M=(Q,\sum,\Gamma,\delta,q,F)$ where: $Q=\{q,s\}$; $\sum=\{a,b\}$; $\Gamma=\{B\}$; $F=\{s\}$; and the transition function $\delta$ is defined as follows $$[q,a,\lambda,s,B] \\ [s,a,\lambda,s,\lambda] \\ [s,b,B,s,\lambda]$$ (Recall that $M$ is defined so as to accept by final statement and empty stack)

$\textbf{(a)}$ List $4$ distinct strings that belong to $L$. If this is impossible, state it and explain why.

Answer: $ab,aab,aba,aaba$

$\textbf{(b)}$ Write a regular expression that defines $L$. If such regular expression does not exist, prove it.

user2879618
  • 21

1 Answers1

1

Recall that $\delta$ is a function from $Q \times (\Sigma \cup \{\lambda\}) \times \Gamma$ to $\mathsf{P}_{\text{fin}}(Q \times \Gamma^*)$, where $\mathsf{P}_{\text{fin}}(A)$ is the set of all finite subsets of $A$. Another way of writing $\delta$ is as a relation over the product of $Q \times (\Sigma \cup \{\lambda\}) \times \Gamma$ and $\mathsf{P}_{\text{fin}}(Q \times \Gamma^*)$, which can be thought of as a quintuple. Using your instructor's notation,

$$ \begin{align} & [q,a,\lambda,s,B] && \text{means} && \delta(q,a,\lambda) = \{(s,B)\} \\ & [s,a,\lambda,s,\lambda] && \text{means} && \delta(s,a,\lambda) = \{(s,\lambda)\} \\ & [s,b,B,s,\lambda] \quad && \text{means} && \delta(s,b,B) = \{(s,\lambda)\} \end{align}$$

emi
  • 1,640
  • regular expression for this is aaba, I do not see how teacher comes up with this regular expression ? – user2879618 Nov 24 '13 at 02:05
  • Unless I'm missing something about your instructor's or textbook's notation, that isn't a regular expression for the automaton in question. For instance, the input ab is rejected by the automaton (as far as I can tell, and interpreting the notation as above). But don't take my word for it - try running the automaton on some strings in the language of $a^+ba^*$ for yourself! – emi Nov 24 '13 at 02:48
  • Actually, if $[s,a,\lambda,s,\lambda]$ lets you transition from an arbitrary stack - a "free move" - to $s$ without affecting the stack, then $a^+ba^*$ is the language of the automaton. But that's not a convention I'm familiar with. – emi Nov 24 '13 at 02:59