Reference no: EM13684091

1. Give context-free grammars that generate the following languages. In all parts, the alphabet Σ = {0,1}.

(a) (0ⁱ1^j| i, j ≥ 0 and i ≤ j + 3}
(b) The empty set
(c) {0ⁱ1^j| i, j 0 and i ≠ j}
(d) {0ⁱ1^j| i,j 0 and 2i ≤ j ≤ 3i }

2. Transform the following grammar into Chomsky normal form Note: Show all the steps.

S → AbB|A
A → aBA | B
B → bAb | ε

Remark: Even though submitting 5 rejected and 5 accepted strings is not required, it is highly recommended. Think of the process as unit/conformance testing of your design/between your designs

3. Submit a JFLAP file of your CFG and a print out on your answers showing 2 different parse trees)

Use JFLAP to show that the following grammar is ambiguous.

S → aSbS | bSaS | ε

4. Use the procedure developed in Lemma 2.21 to convert the following CFG to its corresponding PDA

    S → aSb | bSa | a | b

5. Give the state diagram of pushdown automaton for the following languages.

(a) (ω  ∈ {a, b}" | n_a(ω) = n_b(ω)}

where n_x(ω) is the number of occurrences of x in ω

(b) { aⁱ b^jc^k | i, j, k ≥ 0 and i + j = k}