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\geq 0\}$, where exponents represents the number of repeated occurrences

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

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

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

Example 2

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

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

Type 3 Language

Example 3

Give a grammar that generates the set $\{0^{n}1^{n}2^{n}|n\geq 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\rightarrow a,\ A\rightarrow a,\ A\rightarrow AB$ becomes $\langle A\rangle ::=\langle A\rangle b~|~a~|~\langle A\rangle \langle B\rangle$