Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Math Help - Stack automata

  1. #1
    Super Member
    Joined
    Jun 2008
    Posts
    829

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jun 2008
    Posts
    829
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    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".
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jun 2008
    Posts
    829
    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 ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Jun 2008
    Posts
    829
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    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
    ...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Jun 2008
    Posts
    829
    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    (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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Jun 2008
    Posts
    829
    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
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    This looks about right.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Jun 2008
    Posts
    829
    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)??
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member
    Joined
    Jun 2008
    Posts
    829
    OK. Thank you
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Height of chimney stack using Angles of Elevation
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: April 30th 2011, 12:10 AM
  2. Automata
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: July 6th 2010, 07:20 AM
  3. Stack Variables & Simplex Tableau
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: November 4th 2008, 06:19 AM
  4. Stack Variables & Simplex Tableau
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: November 3rd 2008, 02:44 PM
  5. Stack-Sortable Permutations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 10th 2008, 07:51 PM

Search Tags


/mathhelpforum @mathhelpforum