retagged by
10,463 views
32 votes
32 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 ___________

retagged by

2 Answers

Best answer
33 votes
33 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 }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.

selected by
5 votes
5 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
Answer:

Related questions

12 votes
12 votes
4 answers
3
17 votes
17 votes
4 answers
4
Arjun asked Feb 18, 2021
15,326 views
Consider the following matrix.$$\begin{pmatrix} 0 & 1 & 1 & 1\\ 1& 0& 1 & 1\\ 1& 1 & 0 & 1 \\1 & 1 & 1 & 0 \end{pmatrix}$$The largest eigenvalue of the above matrix is __...