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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ 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\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\}$ Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T=\{0,1\}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ 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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \rightarrow a,\ A \rightarrow a,\ A \rightarrow AB} becomes $\langle A\rangle ::=\langle A\rangle b~|~a~|~\langle A\rangle \langle B\rangle$