Computer Science Concepts - Test 6 (PDA)

  1. Which of the following languages CANNOT be defined by Finite Automata?

    1. {ab, abab, ababab, abababab, ......}

    2. {abb, aabbbb, aaabbbbbb, aaaabbbbbbbb, ......}

    3. {a, b, aa, bb, aaa, bbb, aaaa, bbbb, ......}

    4. {a, aa, aba, abba, abbba, abbbba, abbbbba, ......}

    check/hide answer

  2. The following four statements describe differences between Finite Automata and Pushdown Automata. Three of them are correct. Which one is incorrect?

    1. Finite Automata can only have a finite number of states while Pushdown Automata can have an infinite number of states.

    2. Pushdown Automaton = Finite Automaton + a stack

    3. Finite Automata cannot count while Pushdown Automata can.

    4. In Finite Automata, a transition is represented by 3-tuple

      (state, symbol, new_state);

      in Pushdown Automata, a transition is represented by 5-tuple

      (state, symbol, stack_value, stack_operation, new_state).

    check/hide answer

  3. In Pushdown Automata, the following diagram means that at the state s1, if input symbol is x and y is the top stack symbol, then we can push symbol z onto stack and move to the new state s2. 

        ____                 ____
   /    \ x,y/push(z)   /    \
   | s1 |-------------->| s2 |
   \____/               \____/
    However, sometimes we see a diagram similar to the above one except that the top stack symbol is omitted, i.e. 
        ____                 ____
   /    \ x,_/push(z)   /    \
   | s1 |-------------->| s2 |
   \____/               \____/
    How do you interpret this case?

    1. When the top stack symbol is omitted, it means that the stack must be empty.

    2. When the top stack symbol is omitted, it means that we don't care what the top stack symbol is.

    3. x,_/push(z) means x,x/push(z)

    4. x,_/push(z) means x,z/push(z)

  4. Continuing from the last question. In Pushdown Automata diagram, we sometimes see the input symbol is ^ (lambda), i.e. 
        ____                      ____
   /    \  ^,y/push(z)       /    \
   | s1 |------------------->| s2 |
   \____/                    \____/

    How do you interpret this case?

    1. When the input symbol is ^, it means that we don't consume any symbols in this transition.

    2. When the input symbol is ^, it means that the input string must be empty.

    3. ^,y/push(z) means y,y/push(z)

    4. ^,y/push(z) means z,z/push(z) 

    


                                a,_ /push(a)
                                    _____
                                   |     |
                                   v     |
  ____            ____  a,_/nop   ____   |            /====\
 /    \  push($) /    \          /    \__| ^,$/nop   //    \\
 | s1 |----------| s2 |--------->| s3 |------------->|| s4 ||
 \    /          \    /       ___\    /              \\    //
  ~~~~            ~~~~       |    ~~~~                \====/
                             |     ^
                             |_____|
                            b,a/pop
  5. Which of the following strings are NOT accepted by the above Pushdown Automaton?

    1. a

    2. aab

    3. aba

    4. ab

Rong Yang,