Statement of Fact
Givens
Axioms
Axioms
Grammars
Structure of grammar L is a language over an alphabet A then a grammar for L α → β α = strings of symbols taken from language A β = strings of symbols from a grammar disjoint from A. Can be interpreted as: replace α by β α produces β α rewrites β α reduces β --- Start symbol S → β Ex. Let A = { a, b, c }. S → Λ | aS | bS | cS Ex. Set of binary numerals that represent odd numbers O → B 1 B → Λ | B 0 | B 1. --- S → AB A → Λ | aA B → Λ | bB. Leftmost derivation S ⇒ AB ⇒ aAB ⇒ aaAB ⇒ aaB ⇒ aabB ⇒ aab . Rightmost Derivation S ⇒ AB ⇒ AbB ⇒ Ab ⇒ aAb ⇒ aaAb ⇒ aab . --- The Language of a Grammar (3.3.4) If G is a grammar with the start symbol S and the set of terminals T , then the language of G is the set L ( G ) = { s | s ∈ T * and S ⇒ + s }. Three simple grammars 1. {Λ, a, aa , …, a n , … } = { a n | n ∈ N}. • S → Λ | aS . 2. {Λ, ab, aabb , …, a n b n , … } = { a n b n
Comments
Post a Comment