Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 331

11.2 Construct the grammar for the given language and identify the types of language.
(i)L = {an b an | n ≥ 1} (ii)L = {am b an | m, n ≥ 1}
(iii)L = {an^2 | n ≥ 1}
11.3 Construct the CFG which generates following languages.
(i) L = {0i 1 j 2 k | i = j + k}(ii) L = {0i 1 j 2 k | i < j or i > k}
(iii) L = {0i 1 j 2 k | i ≠ j + k}(iv) L = {0i 1 j | i ≤ j ≤ 1.5 i}
11.4 Show that given grammars are regular grammars. Find the regular expressions for each gram-
mar.
(i)S → aP/aS, P → bQ, Q → aQ/a (ii)S → aA/a, A → aA/bB/a, B → bB/c
(iii)S → 0A, A → 0A/0B, B → 1C, C → 0B/0.
11.5 What language is generated by the following grammars.
(i)S → a S b/b S a/∈ (ii)S → a S b/b
(iii)S → a B/b B/∈, B → a/b B
(iv)S → 0A/1C/b, A → 0S/1B, B → 0C/1A/0, C → 0B/1S
(v)S → 1S/0A/ ∈, A → 0A/1B/1, B → 1S.
11.6 Construct the grammar for the number representations, viz.
(i) Integer numbers (ii) Real numbers
(iii) Floating Point numbers.
11.7 Shows following grammars are ambiguous grammar.
(i)S → 0S1S/1S0S /∈ (ii)S → SS/0/1
(iii)S → P/Q, P → 0P1/01, Q → 01Q/∈ (iv)S → PQP, P → 0P/∈, Q → 1Q/∈
(v)S → aS/aSbS /c (vi)S → AbB, A → aA/∈, B → aB/bB/∈
11.8 Find the equivalent unambiguous grammar from the ambiguous grammars shown from previ-
ous exercises 11.7.
11.9 Show that following languages are not CFL.
(i) L = {0n 1 n 2 n | n ≥ 1} (ii) L = {0n 1 n 2 m | m > n}
(iii) L = {0n 1 m 2 l | n ≤ m ≤ l}(iv) L = {0n 12 n 2 n | n ≥ 0}
(v) L = {0n 1 m 2 l | n ≠ m, m ≠ l, and l ≠ n}(vi) L = {0n 1 m | m = n^2 }
(vii)L = {s s/s ∈ {a, b}}.
11.10 Show that language L = {0n 1 n | n ≥ 1} is derived from the grammar S → 0 S 1, S → 0 1.
11.11 Show that language L = {w wR | w ∈ {0, 1}} is derived from the grammar S → 0 S 0, S → 1 S 1,
S → ∈.
11.12 Show that following languages are CFL.
(i)L 1 = {0n 1 n 2 m | n ≥ 1, m ≥ l} (ii)L 2 = {0n 1 m 2 m | n, m ≥ l}
11.13 Let two grammars G 1 and G 2 are given below. Show that there languages be L 1 and L 2 shown in
exercise 11.12.
(i)G 1 S → AB
A → 0A1/01
B → 2B/2
(ii)G 2 S → CD
C → 0C/0
D → 1D2/12
11.14 From the given CFG G, convert into CNF.
(i)S → SS/(S)/∈
(ii)S → bA/aB, A → bAA/aS/a, B → aBB/b