Notices
Results 1 to 6 of 6

Thread: In desperate need of guidance about an pushdown-automata

  1. #1 In desperate need of guidance about an pushdown-automata 
    Forum Freshman
    Join Date
    Apr 2011
    Location
    Stockholm, Sweden
    Posts
    8
    Hello

    Criteria for automata

    1. M1= 〈K, Σ, Γ, Δ, s, F〉
    K = {q0,q1},
    Σ = {a,b},
    Γ = {A},
    Δ = {((q0,a,ε),(q0,A)),((q0,b,A),(q1, ε)),((q1,b,A),(q1, ε))},
    s = q0, (s = starttillstånd)
    F = {q0,q1}


    What I have manage to do - http://img96.imageshack.us/i/automata.png/

    I got a feeling that I have done something wrong. If so please tell me what I have done wrong and what possibly I have missunderstood.

    Please just guidance and not the complete answer.

    Please help me. Thanks alot!


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    It looks like you put an extra transition rule in. There's only 3 in the description you gave, but 4 in your picture.


    Reply With Quote  
     

  4. #3  
    Forum Freshman
    Join Date
    Apr 2011
    Location
    Stockholm, Sweden
    Posts
    8
    Quote Originally Posted by MagiMaster
    It looks like you put an extra transition rule in. There's only 3 in the description you gave, but 4 in your picture.
    Yes I have fixed that. What I really wonder about now if the automat should allow a or b as first character input. Currently the character a is only allowed as first input.
    Reply With Quote  
     

  5. #4  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    No. Both in the description and the picture, you can have b as the first input and it'll still be lead to a accept state.
    Reply With Quote  
     

  6. #5  
    Forum Freshman
    Join Date
    Apr 2011
    Location
    Stockholm, Sweden
    Posts
    8
    Quote Originally Posted by MagiMaster
    No. Both in the description and the picture, you can have b as the first input and it'll still be lead to a accept state.
    After having the automata edited it looks like this - http://img839.imageshack.us/i/automatau.png/ To match more to the criteria right?

    and it won't accept an "b" as first input since then it needs to pop an "A" which then have not been written to the stack so an "A" can't be possibly popped from stack since there is no "A" in stack. This leads to that the automata only accepts an "a" as first input. When the first input is "a" then "A" is written to the stack so it then will allow "b" as input to pop the "A" which was written to stack when input "a" was made.

    but due to the criteria of the automata Σ = {a,b},

    shouldn't the automata both accept "a" or "b" as first input? an d if yes how to do that? ALso I am not sure if the automata should start with an "A" before any input is done to the automata?

    Thanks
    Reply With Quote  
     

  7. #6  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Oh yeah. You're right. I overlooked that. But no, not every possible input has to be accepted. Generally, it's assumed that any invalid inputs lead to a hidden fail state with no way out. (Meaning the automaton will never accept after receiving an invalid input.)
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •