Log In
2 votes

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 ___________

in Theory of Computation
edited ago by
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?

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.

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.

2 Answers

0 votes

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

edited by

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.
0 votes

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 }n\geq m+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)…(51,49)\}$ which in total there are $50$. Try for $(m=50, n=50)$ to better understand why it isn’t accepted.

edited ago by

Related questions

0 votes
2 answers
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
asked Feb 18 in Graph Theory Arjun 379 views
0 votes
3 answers
Consider the following undirected graph with edge weights as shown: The number of minimum-weight spanning trees of the graph is ___________.
asked Feb 18 in Algorithms Arjun 417 views
1 vote
2 answers
The lifetime of a component of a certain type is a random variable whose probability density function is exponentially distributed with parameter $2$. For a randomly picked component of this type, the probability that its lifetime exceeds the expected lifetime (rounded to $2$ decimal places) is ____________.
asked Feb 18 in Probability Arjun 476 views
3 votes
1 answer
There are $6$ jobs with distinct difficulty levels, and $3$ computers with distinct processing speeds. Each job is assigned to a computer such that: The fastest computer gets the toughest job and the slowest computer gets the easiest job. Every computer gets at least one job. The number of ways in which this can be done is ___________.
asked Feb 18 in Combinatory Arjun 808 views