in Theory of Computation retagged by
10,414 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 ___________

in Theory of Computation retagged by
by
10.4k views

4 Comments

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.
1
1
can anyone tell me whether given PDA is DPDA or NPDA?
0
0

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

0
0

2 Answers

33 votes
33 votes
Best answer

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

4 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?

0
0

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 .

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

2 Comments

How

a>b in PDA

Please explain where I am missing
0
0
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.
6
6
Answer:

Related questions