someone help.

Dark Mode

6,003 views

17 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 ___________

1

19 votes

Best answer

**Correct Answer: 50**

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

**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**.- $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.
- 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.
- 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.

0

**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

3 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**