Search code examples
formal-languages

Formal Language Npda graph

I'm trying to Draw a npda for this language but cant seem to get it

enter image description here

I want to know how to Write the sequence of moves done by the npda for the input sequence w = aacb. and Is the string w accepted?

thanks I just cant seem to do this

Solution
    1. Read at least two a's without touching the stack. Crash if you see anything else.
    2. Continue reading a's and pushing one a onto the stack for each a you read.
    3. If you read a c, then you must read a b immediately afterward or crash. Do not change the stack.
    4. If you read a b, prepare to begin reading (ac) over and over again. Do not change the stack.
    5. If the stack is not empty, you must read an a and then c or crash. If you do read a and then c, pop a single a from the stack.
    6. Continue until you crash or the stack becomes empty after reading (ac) multiple times. If the input is exhausted, accept. Otherwise, crash.

    Please let me know if you would like to see a state transition diagram to make this more concrete. I encourage you to try writing your own first.