GATE CSE 2021 Set 1 | Question: 51

Question

In a  pushdown automaton $P=(Q, \Sigma, \Gamma, \delta, q_0, F)$, a transition of the form,

where $p,q \in Q$, $a \in \Sigma \cup \{ \epsilon \}$, and $X,Y \in \Gamma \cup \{ \epsilon \}$, represents $$(q,Y) \in \delta(p,a,X). $$Consider the following pushdown automaton over the input alphabet $\Sigma = \{a,b\}$ and stack alphabet $\Gamma = \{ \#, A\}$.

The number of strings of length $100$ accepted by the above pushdown automaton is ___________

Comments

First transition puts $\#$ on stack top. Then in $q_1$, they have a transition labelled $a, \epsilon → A$. Shouldn’t it be $a, \# → A$ as stack top has $\#$? And then there would need to be an extra transition that does $a, A → AA$.

What am I missing?

---

pritishc

yeah its confusing for sure but what they mean is without seeing anything on stack you can push A on reading a.

---

$L = \{ a^n b^m | n >  m \ \& \ n+m=100 \}$

$L = { a^{51} b^{49} ,….. , a^{99}b, a^{100}}$

$|L| = 50$

for reaching q3 from q2 there must be “A” on the top of the stack, hence $n > m$.

---

In the given automata the transition from q0 to q1 pushes ‘#’ on the stack. As there is no transition from q1 that sees ‘#’ on stack top. I believe that the given automata doesn’t accept any language.

answer: 0

---

@Mk Utkarsh can you please point to a standard problem set that has your kind of PDA interpretation (i.e. “without seeing anything on stack, push A” given in a transition diagram)? I am confused because I haven’t seen anything like this before...atleast I don’t remember. But I’m seeing a lot of people use your interpretation of PDA spec.

@mayankso I gave the same answer but not sure.

---

As there is no transition from q1 that sees ‘#’ on stack top. I believe that the given automata doesn’t accept any language.

 

https://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/17/Small17.pdf

---

Thanks bro. TIL

---

I felt the same thing. The first transition pushes # into the stack, there are no transitions with # on top of the stack again. I also gave zero as answer. Donno how others are getting 50.

---

what does the transition between q1 and q2 tell ,is it to pop ?

someone help.

---

L = {aᶦ bʲ | i>j,j>=0 } ;
for string length 100, i+j = 100;

i = 100 – j;
as i>j, j<100-j;
2j<100;
j<50, for string length 100, i.e, 0<=j<=49.

---

can anyone tell me whether given PDA is DPDA or NPDA?

---

@KathanVakharia given PDA is non deterministic (NPDA) . Easy way to identify NPDA is if you see epsilon in input. Like E,A/A. 

Answer 1

Correct Answer: 50

---

A detailed analysis of the given Automaton(skip if you’re comfortable with PDAs):

1. PDAs accept strings either by emptying the stack or by reaching the final state after reading the entire input tape. In this example, the transitions from initial state $q_0\to q_1$  is marked by pushing $\#$ into the stack and is the only transition that involves $\#$ and can’t be popped out again. So, there is no chance of acceptance by emptying the stack rather it’s only by reaching the final state.
2. $a’s$ can only be accepted in state $q_1$ and $b’s$ only by state $q_2$ this implies the string must be of the form $\{a^mb^n\}$ for now.
3. To read $b’s$ from the input tape, we’ve to pop-out $A$ each time which’s obtainable from accepting a’s. So, the number $b’s<a’s$ for all the $b’s$ to be accepted in this state.
4. To reach the final state we need at least one $A$ to make the transition to the final state although it’s funny about $A$ not being spent.

Note: Reading $\epsilon$ from stack doesn’t use up any of the stack contents just like $\epsilon$ transitions in a conventional FAs.

---

The given automaton accepts strings of the form $\{a^mb^n, \text{where }m\geq n+1\}$. And, it’s given the question that $m+n=100$.

So the possible set values in the form of $(m,n)$ are $\{(100,0),(99,1),\ldots,(51,49)\}$ which in total there are $50$. Try for $(m=50, n=50)$ to better understand why it isn’t accepted.

Comments

Doubt 1: On reaching final state can it happen like there is still input left to be checked?

For eg:Consider language over $\sum$(a,b) such that it contains all the strings starting with a then it possible that while checking string abbb directly by seeing a we can go to final state? Can someone explain by drawing a dfa also?

 

Doubt 2: Is it always true that we can go to final state only by seeing Epsilon in a PDA which accepts language by using final state?

---

Doubt 1 Ans- Yes it can be happen that on reaching final state there can be input left in this case string will not be accepted.

Doubt 2 Ans- Yes we can go to final state by seeing the Epsilon  in PDA bt again if your input symbols are still left the string will not be accpted .

---

IN State q1, can anyone please explain  . $a,\epsilon \rightarrow A$

It should only take the first a as i/p and NOT the remaining a na?

For that we need $a,a \rightarrow A$

Answer 2

Pushdown automata accept string of

(a^n b^n | a>b and a+b=100) 

Conditions to accept string is a is greater then b and a+b = 100

So only 50 string can generate by this automata

a will be (51 to 100) because a can not less then b and b (0 to 49) always less then a

Example a^99b^1 to a^51b^49

Ans is 50

Comments

How

a>b in PDA

Please explain where I am missing

---

In given PDA, for transition from q$_{2}$ to q$_{3}$(final state), it requires symbol A to be at top. It is possible only when a > b.