transition function DFA, PDA

435 Views Asked by At

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.

1

There are 1 best solutions below

3
On

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}$$