MHB Describe a language accepted by a pushdown automata.

  • Thread starter Thread starter JamesBwoii
  • Start date Start date
  • Tags Tags
    Automata Language
AI Thread Summary
The discussion revolves around defining a specific language based on a stack-based automaton's behavior. The initial understanding involves pushing an 'A' onto the stack in the start state and transitioning to a final state 'f' upon receiving a 'B', which pops 'A' from the stack. The user initially considered the language to be represented as {a^n b^n | n ≥ 0}, but later doubts this characterization. Another participant clarifies that the automaton can only accept an 'A' initially, followed by 'B's, leading to an empty stack at the final state. The conclusion drawn is that the language can be described as {ab}, indicating a sequence of one 'A' followed by one 'B'.
JamesBwoii
Messages
71
Reaction score
0
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.
 

Attachments

  • Capture.PNG
    Capture.PNG
    6.5 KB · Views: 105
  • SOzGksL.jpg
    SOzGksL.jpg
    92.3 KB · Views: 107
Technology news on Phys.org
JaAnTr said:
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.
 
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!
 
Last edited:
JaAnTr said:
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\}$.
 
Oh ok thanks, that makes sense. :D
 
Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
I have a quick questions. I am going through a book on C programming on my own. Afterwards, I plan to go through something call data structures and algorithms on my own also in C. I also need to learn C++, Matlab and for personal interest Haskell. For the two topic of data structures and algorithms, I understand there are standard ones across all programming languages. After learning it through C, what would be the biggest issue when trying to implement the same data...
Back
Top