TOC-Context Free Language

Context Free Language

A context-free grammar (CFG) is a 4-tuple , where

  • is a finite set called variables;
  • is a finite set called terminals;
  • is a finite set of production rules with each in the form
    where is a variable and is a string of variables and terminals; and
  • is the start variable.
Definition: CFL

A language is context-free if exactly all strings in the language can be produced by a context-free grammar.

Theorem

A language is context-free if and only if it is recognized by a PDA.

Ambiguous

A parse tree shows the structure of a string (sentence). However, CFG is strongly enough to create ambiguous.

Definition: Ambiguous

A grammar is ambiguous if a string in the language defined by the grammar can be presented by multiple parse trees with different structures.

Also, checking whether a CFG is ambiguous is undecidable.
Meaning that there is NO algorithm / machine which can tell an arbitrary CFG is ambiguous or not.

Properties

Equivalence

Theorem

A language is context-free if and only if it is recognized by a PDA.

Let be an arbitrary context-free language.
By the definition of CFL, has a CFG generating it.
Then, we prove the theorem by introducing a conversion algorithm from to a PDA which recognizes and vice versa.

CFG to PDA

To construct the PDA from , let w be a string in L.

  • generates by a sequence of productions.
  • We construct to simulate this procedure.
  • generates some strings and pushes them into the stack.
  • Then, tries to match the stack with .

In detail, P does the following things.

  1. Push $ and the start variable into the stack ($ first and E second).
  2. Repeat the followings.
    • If a variable is on top of the stack, nondeterministically select the rules starts from A and replace A by the RHS of the rule (in the stack).
    • If a terminal a is on top of the stack, check the next input symbol. If yes, continue; otherwise reject.
    • If $ is on the top, accept the string if all symbols of w have been read; reject otherwise.

Formally, let be a CFG. Construct the following transitions.

  4. For each production rule in the form of , where ; construct the followings:
      1. ;
      1. for
  5. For each production rule .
  6. For each terminal .

The PDA is called parser, which is used in compilers.

PDA to CFG

Now let's convert an arbitrary PDA to a CFG .
First, we modify .

  • has a single final state . If it has multiple accepting states, create some artificial transitions to one of the accepting states.
  • The stack of is always empty when a string is accepted. If the stack is non-empty, create an artificial state to pop out everything in the state.
  • Every transition either pushes a symbol or pops out a symbol (not both, not none). If a transition is , create an artificial state and replace the transition by and

Formally, Let . The construction of is as follows:

  • The set of nonterminals is .
  • The set of terminals is .
  • The initial symbol is .
  • The production rules are of three types:
    • , if there exist transitions and , then add to .
    • , add to .
    • , add .

Limitation

Closure Properties

Context-free and Regular

Table Of Contents
TOC-Context Free Language
Context Free Language
Ambiguous
Properties
Equivalence
CFG to PDA
PDA to CFG
Limitation
Closure Properties
Context-free and Regular