What am I missing?

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 ___________

0

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?

What am I missing?

1

yeah its confusing for sure but what they mean is without seeing anything on stack you can push A on reading a.

1

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

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

1

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

answer: 0

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.

@mayankso I gave the same answer but not sure.

0

As there is no transition from q1 that sees ‘#’ on stack top. I believe that the given automata doesn’t accept any language.

https://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/17/Small17.pdf

0 votes

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

0 votes

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