Algebra
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 ∈...
Comments
Post a Comment