CSCE 222 Lecture 27

« previous | Monday, April 11, 2011 | next »

Chomsky's Classification of Grammars

4 types of production rules:

• Type 0. no restrictions on production rules
• Type 1. "context-sensitive grammar" Productions are of the form lAr → lwr, where A ∈ N, l,r ∈ V*, and w ∈ V* (≠ λ)
• Type 2. "context-free languages" Productions are of the form A → w when A ∈ N
• Type 3. "regular languages" Productions are of the form A → aB when A,B ∈ N and A → a when a ∈ T

Example 1

Give a grammar that generates the set $\{0^n{1}^n|n\ge 0\}$, where exponents represents the number of repeated occurrences

Solution: $G=(V,T,S,P)$

• $V=\{0,1,S\}$
• $T=\{0,1\}$
• $P=\{S\to \lambda ,S\to 0S1\}$

This is a "Type 2 (context-free) language"

Example 2

Give a grammar that generates the set $\{0^n{1}^m|m,n\ge 0\}$.

Solution: $G=(V,T,S,P)$ $V=\{0,1,S,A\}$ $T=\{0,1\}$ $P=\{S\to 0S,S\to 1A,A\to 1A,A\to \lambda ,S\to \lambda \}$

Type 3 Language

Example 3

Give a grammar that generates the set $\{0^n{1}^n{2}^n|n\ge 0\}$.

This is a context-sensitive language (cannot be generated by any context-free language

Parsing Languages

2 ways:

• Top-down: Start with start symbol and use production rules to produce the desired output
• Bottom-up: Start with desired output and reverse-engineer to a start symbol

Backus Naur Form

When non-terminal symbols can be replaced by many options, Backus Naur form combines them:

$A\to a,A\to a,A\to AB$ becomes $⟨A⟩::=⟨A⟩b|a|⟨A⟩⟨B⟩$