CSC444 Oct16

slide version

single file version

Contents

1. Example Context-Free Language
2. Grammar
3. An attempt at a formal automaton for CFLs
4. Deterministic Push Down Automaton
5. Automaton for the Example Grammar
6. LL(1) grammars and Automata
7. Bad Grammar
8. Push-Down Automaton (PDA)
9. Non-determinism
10. Example
11. Alternate Notation
12. Determining that the stack is empty
13. Running a PDA
14. Augmented Grammars
15. Using JFLAP
16. Derivation
17. Example PDA Run
18. Exercises

Example Context-Free Language[2] [top]

   L = { anbn | n >= 1 }

We know this languge is not regular by the pumping lemma for regular languages.

It is, however, a context-free language (CFL).

What is a grammar for L?

Grammar[3] [top]

    G = ({S}, {a,b}, S, R) where the set of rules R is

    S -> a S b | a b

An attempt at a formal automaton for CFLs[4] [top]

For regular languages we had two equivalent automata:

1. DFA
2. NFA

These are equivalent in the sense that the languages recognized by some DFA is the same as the set of languages recognized by some NFA.

So it would seem likely that the same situation might occur for context-free languages and corresponding automata; deterministic and non-deterministic versions.

Deterministic Push Down Automaton[5] [top]

Informally a push down automaton

• is a finite state automaton together with a stack and a stack alphabet.
• from the current state and the next input, the transition function determines the next state and also performs an operation on the stack pushing a value on the stack, popping one off.
• An input string is accepted if after the input is read, the automaton is in a final state and the stack is empty.

Automaton for the Example Grammar[6] [top]

For the input string aaabbb

• for each a read, the new state is q₁ and an x is pushed on the stack
• For each b read the new state is q₂ and an x is popped off the stack

So 3 x's are pushed on the stack.

Then 3 x's are popped off the stack.

The machine halts in state q₂

The string is accepted.

What would happen for aaabbbb? or for aaabb?

LL(1) grammars and Automata[7] [top]

For grammars that are LL(1) and even for a slightly larger class of context-free grammars, the languages can be recognized by some deterministic push down automaton.

However, this is not true for every context-free grammar.

The kind of automaton that is needed to recognized a CFL in general is non-deterministic.

Bad Grammar[8] [top]

 S -> a S a | b S b | ε

The language is 
 { wwR | where w is in {0,1}* and wR is the reverse of w }

 E.g, aabaabaa and abbbbbba

 Problem for the automaton: Where is the middle?

Push-Down Automaton (PDA)[9] [top]

Non-determinism[10] [top]

This definition of a Push Down Automaton (PDA) is non-deterministic since the transition function has values in the power set of Q x Γ_ε

Where are the push and pop operations?

Is there a way for the automaton to specify the stack should be empty?

Is there a way for the automaton to specify 'eof', that is no more input remaining?

Example[11] [top]

1. The stack initially has one symbol: Z
2. Transition label a;Z;xZ means on input a, the top of the stack should be Z, which is popped and the two symbols xZ are pushed back on the stack.

The notation and conventions in the diagram are specific to the JFLAP program.

JFLAP = Java Formal Language and Automata Package

JFLAP is by Professor Susan Rodger, Duke University, and her students. It is available at http://www.jflap.org

Alternate Notation[12] [top]

This is the notation Sipser uses.

    Here e represents ε (JFLAP uses λ instead of ε)
  
    Transition label a, b -> c  means
    1. read input symbol a
    2. the top of the stack should be 'b'; replace it with 'c'

    Note: either b or c can be ε

    a, ε -> c  means 
    1. read a
    2. push c

    a, b -> ε means
    1. read a
    2. pop b
    

Determining that the stack is empty[13] [top]

The definition of the operation of the non-determinisitic PDA doesn't directly have a way of checking that the stack is empty when the input has all been read.

So this is simulated by initially pushing a sentinel value on the stack without reading any input.

    Add a new start state if necessary with this transition to the
    original intended start state

        ε, ε -> $

In JFLAP, instead of adding a new start state, that step is essentially done automatically.

    1. Instead of $, JFLAP uses Z
    2. Instead of beginning with an empty stack, JFLAP starts with Z
    on the stack.

Pushing on the stack must be formulated in terms of the transition function

How do you read 'a' and achieve the effect of popping 'S' and pushing three symbols x1 x2 x3 on the stack?

Running a PDA[14] [top]

Formally a PDA accepts an input string w if

Augmented Grammars[15] [top]

The sentinel, Z, that JFLAP places on the stack initially as a counterpart in context-free grammars.

It is called augmenting the grammar.

    S -> a S a | b S b | ε

Agumented grammar:
    1. Add a new start symbol, P, the sentinel, Z, and
    2. One new rule P

          P -> S Z

Revised grammar:

          P -> S Z
          S -> a S a | b S b | ε

Using JFLAP[16] [top]

We can use JFLAP with the grammar above to see the non-determinism in action.

The PDA for any context free grammar is constructed like this:

1. Create 3 states q_start, q_loop, and q_accept
2. Push the right side of the augmented grammar rule on the stack on ε input from the start state and go to q_loop
3. Add one loop transition for each grammar rule to state q_loop
4. Add one transition from q_loop to q_accept for ε input and popping the sentinel Z off the stack.

Derivation[17] [top]

Give a derivation for aabbaa using the grammar:

          P -> S Z
          S -> a S a | b S b | ε

Example PDA Run[18] [top]

Now construct the PDA with JFLAP and run it on input aabbaa

Exercises[19] [top]

1. Give a context-free grammar for L = {aⁿbⁿc^m | n >= 0, m >= 0}
2. Exercise 2.9 Give a grammar for L = { aⁱb^jc^k | i = j or j = k where i,j, k >= 0 }
3. Use JFLAP to create a pushdown automata for Exercise 2.9.
4. Exercise 2.14 Convert the following grammar to Chomsky normal form:

     A -> BAB | B | ε
     B -> 00 | ε