I have the following doubts
If I build a Stack Automata on a path that recognizes the language, but the automata does not recognize the other way. Is this correct?
For language: a^nb^ma^{n+m}
q0 => (a,E,X) to q0
q0 => (E,E,E) to q1
q1 => (b,E,X) to q1
q1 => (E,E,E) to q2
q2 => (a,X,E) to q2
q2 => (?,?,E) to q3
q3 is end state
E is empty move
? is empty stack
Works for the language => aabbaaaa
But not work if go this route => aabaaa or abbbaaaa
My question is if the automaton is correct
Thank you. I messed up, are accepted
I think I understand.
For language: a^n b^2n / n>= 0
I make:
q0 => (a,E,X) to q0
q0 => (E,E,E) to q1
q1 => (E,E,X) to q2
q2 => (b,X,E) to q3
q3 => (b,X,E) to q4
q4 => (E,E,E) to q2
q4 => (?,?,E) to q5
q5 is end state
Are correct ?
I think this is wrong. For each a read you add one X to the stack. Then for each b read you remove one X. Therefore, to be accepted, a string must have equal number of a's and b's. The automaton makes sure that the number of b's is even, not that it is twice the number of a's. I don't understand the role of q1, which seems to remove just one X. Maybe it's also possible to eliminate q4 and make q3 go directly to either q2 or q5.
I think that for each a you need to add two X's and for each b to remove one X.
Thank you. You're right, now I've done this:
q0 => (a,E,X) to q1
q1 => (E,E,X) to q0
q1 => (b,X,E) to q2
q2 => (b,X,E) to q2
q2 => (?,?,E) to q3
q3 is end state
I think s right.
For language a^n b^m | n <= m <= 3n
I'm racking my brains, most have not figured out how to do
(1) In this automaton, the only way to move from q0 to q3 is to read a and to push one X on the stack. Thus this a cannot result in reading two or three b's later. For example, I don't think abbb is accepted.
(2) I am wondering from the problem statement if n and m can be zero. This automaton does not accept an empty string.
(3) In "q3 => (?,?,E) to q4", you use the same character ? to denote the symbol to read and the symbol to pop from the stack. In general, the input alphabet and the stack alphabet are different. In your case, for example, the input alphabet can be {a, b} and the stack alphabet can be {X, ?}. Therefore, denoting these two symbols by the same letter is a type error.
Now
q0 => (a,E,X) to q0
q0 => (a,E,X) to q1
q0 => (a,E,X) to q2
q0 => (E,E,E) to q3
q1 => (E,E,X) to q0
q2 => (E,E,X) to q1
q3 => (b,X,E) to q3
q3 => (?,?,E) to q4
q4 is end state
(1)
q0 -> (E,E,E) -> q3... (Empty word)
q0 -> (a,E,X) -> q0 -> (E,E,E) -> q3... (ab)
q0 -> (a,E,X) -> q1 -> (E,E,X) -> q0 -> (E,E,E) -> q3... (abb)
q0 -> (a,E,X) -> q2 -> (E,E,X) -> q1 -> (E,E,X) -> q0 -> (E,E,E) -> q3... (abbb)
(2)
q0 -> (E,E,E) -> q3... (Empty word)
(3)
I use "?" also as a symbol of final word on tape