PDA

Question

Consider the following push down automata.

The language accepted by above PDA is_______.

1. Regular but infinite.
2. DCFL but not regular.
3. CFL but not DCFL
4. Finite language.

Answer 1

Regular but infinite. that is $a(a+b)(a+b)^*b\$$
Initially $Z_0$ is stack initial symbol, at state $q_0$ read $a$ and push $a$ into stack, we have $aZ_0$ in stack, now read $a$ or $b$, do nothing at stack, that is still $aZ_0$, and reach to $q_1$, can read any no of $a$'s or $b$'s at $q_1$ and do nothing at stack, that is still $aZ_0$, and still at $q_1$, read $b$ and pop $a$ from stack, we have $Z_0$ at stack and reach to $q_3$, read $  and do nothing reach to $q_f$.  

Comments

NFA for the above Language

---

Yes.

Answer 2

b) Its clearly not DCFL because on input a there are more than two transition.

d) There is a loop at state q₁ so it  not finite. So its is wrong.

Now option (c) and (a) are the remaining , both are correct but option (a) is more correct with more precise description about the language.

Because given language can be represented using  Regular Expression and Its is the language accepting all the strings of length at least 3 which starts with 'a' and ends with 'b'. 

Regular Expression = a (a+b) (a+b)^* b

So option (a) is correct here.

Comments

cleared bro,thank u

---

q_o on b just changing its state to q₁ not performing any operation on stack.

---

ya,i understood

Answer 3

Yes it will be (A)

the language will be a(a+b)⁺b

Because, First in empty stack it is taking one 'a' at the top of stack.

Now, whatever a or b it takes but it doesnot change the stack value. The stack contain only that 'a'. But it should have to take atleast one more a or b in the string. That is why it goes to state q0 to q1. Now, at last it got one 'b' for going to next state q3 which proceeds to final state qf.

So, here we can form regular expression and also can draw dfa for a(a+b)⁺b . So, it will be infinite regular language. 

Comments

thanx

Answer 4

Its a NDPDA 
At q0 a will be pushed into stack move to q1
At q1 it will read any number of input a and b 
    at q1 we have two choices for input b it can either read the input b only or pop the input a store in the stack 
so the language accepted by PDA = a(a+b)*b  which is regular and infinite.
option A.