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: 106
  • SOzGksL.jpg
    SOzGksL.jpg
    92.3 KB · Views: 110
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
 
Thread 'Star maps using Blender'
Blender just recently dropped a new version, 4.5(with 5.0 on the horizon), and within it was a new feature for which I immediately thought of a use for. The new feature was a .csv importer for Geometry nodes. Geometry nodes are a method of modelling that uses a node tree to create 3D models which offers more flexibility than straight modeling does. The .csv importer node allows you to bring in a .csv file and use the data in it to control aspects of your model. So for example, if you...
I tried a web search "the loss of programming ", and found an article saying that all aspects of writing, developing, and testing software programs will one day all be handled through artificial intelligence. One must wonder then, who is responsible. WHO is responsible for any problems, bugs, deficiencies, or whatever malfunctions which the programs make their users endure? Things may work wrong however the "wrong" happens. AI needs to fix the problems for the users. Any way to...
Back
Top