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 → B1 

B → Λ | B0 | B1.

---

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, …, an, … } = {an | n ∈ N}.

•S → Λ | aS.

2.{Λ, ab, aabb, …, an bn, … } = {an bn | n ∈ N}.

•S → Λ | aSb.

3.{Λ, ab, abab, …, (ab)n, …} = {(ab)n | n ∈ N}.

---

Combining Grammars:

Union Rule: The language M ∪ N starts with the two productions

S → A | B.

Product Rule: The language MN starts with the production

S → AB.

Closure Rule: The language M* starts with the two productions

S → AS | Λ.

---

Reference: Discrete Structures, 4th Edition. Hein