CFG Example 1
The following CFG generate all valid variable (identifier) names in ‘C’ language according to the following rules.
- The variable name can only start with alphabet or underscore
- there is no maximum length for the variable name
- after first character any alphabet, digit, underscore or $ can appear.
S ® XY
X ® alpha | _
Y ® alpha Y| digit Y | _Y | $Y | L
alpha ® A | B| C | … | Z | a | b | c | … | z
digit ® 0 | 1 | 2 | … | 9
CFG Example 2
{ w ∈ {0, 1} ∗ | w contains at least three 1s }
S → X1X1X1X
X → 0X | 1X | ε
CFG Example 3
{ w ∈ {0, 1} ∗ | the length of w is odd and the middle symbol is 0 }
S → 0S0 | 0S1 | 1S0 | 1S1 | 0
CFG Example 4
{ | i, j, k ≥ 0, and i = j or i = k }
S → XY | W
X → aXb | ε
Y → cY | ε
W → aWc | Z
Z → bZ | ε
CFG Example 4
{ | i, j, k ≥ 0 and i + j = k }
S → aSc | X
X → bXc | ε
CFG Example 6
∅
S → S
CFG Example 7
The language A of strings of properly balanced left and right brackets: every left bracket can be paired with a unique subsequent right bracket, and every right bracket can be paired with a unique preceding left bracket. Moreover, the string between any such pair has the same property. For example, [ ] [ [ [ ] [ ] ] [ ] ] ∈ A.
S → ε | SS | [S]
CFG Example 8
Let T = { 0, 1, (, ), ∪, ∗ , ∅, e }. We may think of T as the set of symbols used by regular expressions over the alphabet {0, 1}; the only difference is that we use e for symbol ε, to avoid potential confusion in what follows. (a) Your task is to design a CFG G with set of terminals T that generates exactly the regular expressions with alphabet {0, 1}. Answer: G = (V, Σ, R, S) with set of variables V = {S}, where S is the start variable; set of terminals Σ = T; and rules S → S ∪ S | SS | S ∗ | (S) | 0 | 1 | ∅ | e
S → S ∪ S | SS | S ∗ | (S) | 0 | 1 | ∅ | e