Describe a language accepted by a pushdown automata.

[JamesBwoii]

View attachment 3640

That's the question. I've had a go at drawing a diagram to help me explain it.

View attachment 3641

My understand is that from the start state, an A pushes an A to the stack and stays in the initial state s. Getting a B whilst in state s pops an A from the stack and moves to final state f. Getting a B whilst in state s also pops an A from the stack and remains in state f. And getting an A in the final state whilst A is on the stack remains pops an A from the stack.

How do I describe this language?

I initially thought it might be:

${a^n b^n ∈ {a, b}∗| n ≥ 0}$

but I'm pretty sure that's wrong now.

 

[I like Serena]

View attachment 3640

That's the question. I've had a go at drawing a diagram to help me explain it.

View attachment 3641

My understand is that from the start state, an A pushes an A to the stack and stays in the initial state s. Getting a B whilst in state s pops an A from the stack and moves to final state f. Getting a B whilst in state s also pops an A from the stack and remains in state f. And getting an A in the final state whilst A is on the stack remains pops an A from the stack.

How do I describe this language?

I initially thought it might be:

${a^n b^n ∈ {a, b}∗| n ≥ 0}$

but I'm pretty sure that's wrong now.

Hi JaAnTr,

Your drawing looks good to me!

Initially the stack is empty.
That means only $a$ will be accepted, which will also push $a$ on the stack.
After that $a$ will not be accepted any more, since the top of the stack holds $a$.

So we can only continue with $b$, which will pop $a$ from the stack, leaving the stack empty.

From there there is no valid transition any more, since the stack is empty.
Luckily we're in a final state when that happens.

 

[JamesBwoii]

How would I go about describing the language?

I think it needs to be in the same form as this $ {a^m {b}^{2m} ∈ {a, b}∗| m ≥ 0}$ but obviously it will be a different language.

Thanks!

 

[I like Serena]

How would I go about describing the language?

I think it needs to be in the same form as this $ {a^m {b}^{2m} ∈ {a, b}∗| m ≥ 0}$ but obviously it will be a different language.

Thanks!

At the start we can only accept $a$, and after that only $b$, and then nothing anymore.
So I believe that the language is $\{ab\}$.

 

[JamesBwoii]

Oh ok thanks, that makes sense. :D