6,003 views

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 ___________

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?

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.

edited by
its called jump, in this transition we are neither reading from input string or from stack, nor entering anything into stack.
The range is from $a^{51}b^{49}$ to $a^{100} b^{0}$ because

the language is $\{a^mb^n, \ m\ge n+1, \ m+n = 100\}$. Hence $50$ strings.

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?

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

by

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.