automatacomputation-theorypushdown-automatonautomata-theory

How to construct a pushdown automata for L={a^nb^m where n<=m<=2n}?


It should be constructed without using 2 stacks. I tried it but I couldn't do it without 2 stacks.


Solution

  • Here's the strategy: we can easily make a PDA that accepts a^n b^n, and we can easily make one that accepts a^n b^2n. Our language is a superset of these languages that also accepts anything with a number of b in between n and 2n. We can make use of nondeterminism to allow this as follows: for every a we put onto the stack, we can nondeterministically decide whether to consume one or two b before popping the a. If our NPDA chooses to consume one each time, we get a^n b^n. If it choose to consume two each time, we get a^n b^2n. If it chooses some of both, we get a number of b in between these extremes. We only accept when we exhaust the input with an empty stack.

    Q    s    S    Q'    S'    Comment
    
    q0   e    e    qA    e     Allow empty string to be accepted
    
    q0   a    x    q0    ax    Count a and push onto stack
    q0   e    x    q1    x     Transition to counting b
    
    q1   b    ax   q1    x     Mark off a single b for each a
    q1   b    ax   q2    x     Mark off the first of two b for this a
    q1   e    e    qA    e     Allow string in language to be accepted
    
    q2   b    x    q1    x     Mark off the second of two b for this a
    

    In this PDA we have q0 as the initial state and qA as the accepting state. Processing on aabbb:

       q0, aabbb, e 
    -> q0, abbb, a 
    -> q0, bbb, aa
    -> q1, bbb, aa
    -> q1, bb, a
    -> q2, b, e
    -> q1, e, e
    -> qA, e, e
    

    Of course there are many parsings that don't lead to qA but in an NPDA we accept if there is at least one.