1. ## Stack automata

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?

2. I am not sure I understand the question. A sentence starting with "If" must have a "then" somewhere. What does it mean to build an automaton "on a path"? What does it mean to recognize "the other way"? Recognize what?

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

4. Well, it seems reasonable. Why are you saying that aabaaa and abbbaaaa are not accepted?

"q2 => (?,?,E) to q3" should be "q2 => (E,?,E) to q3".

5. 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 ?

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

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

8. If your automata are nondeterministic, then you can add from one to three X's for each a. Something like this:

q0 => (a,E,X) to q0
q0 => (a,E,X) to q1
q0 => (a,E,X) to q2
q1 => (E,E,X) to q0
q2 => (E,E,X) to q1
...

9. Thank you

I do

q0 => (a,E,X) to q0
q0 => (a,E,X) to q1
q0 => (a,E,X) to q2
q0 => (a,E,X) 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

10. (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.

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

13. Thank you very much

I find a language that I not understand
L = { w E {a,b}^* | Ma(W) is multiple of 3}

What language is that? Word multiple of 3 (bba, bbbbaa, aabbbabab)??

14. I don't know. Maybe Ma(w) is the number of letters a in w, but I don't know what M stands for and I've never seen this notation.

15. OK. Thank you

Page 1 of 2 12 Last