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 |
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
{ a^i b^j c^k | 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
{ a^i b^j c^k| 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