## 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

** **