07 Exercises2
Uploaded by
ghmpersonal07 Exercises2
Uploaded by
ghmpersonalExercises 2
1
Section 4.1
Exercise 2
• Let L1 = L(ab*aa), L2 = L(a*bba*).
• Find a regular expression for (L1 ∪ L2)*L2.
2
Section 4.1
Exercise 21
• The tail of a language is de ned as the set of all su xes of its strings, that is
• tail(L) = {y : xy ∈ L for some y ∈ Σ*}.
• Show that if L is regular, so is tail(L).
3
fi
ffi
Section 4.2
Exercise 9
• Exhibit an algorithm that, given any three regular languages, L, L1, and L2,
determines whether or not L = L1L2.
4
Section 4.3
Exercise 4
• Show that the language language L = {w : na(w) = nb(w)} is not regular.
5
Section 4.3
Exercise 6 (a)
• Determine whether or not the following language on Σ = {a} is regular:
n
• L = {a : n ≥ 2, is a prime number}.
6
Section 4.3
Exercise 11 (b)
• Consider the language
n
• L = {a : n is not a perfect square}.
• Show that this language is not regular by applying the closure properties of
regular languages.
7
Section 5.1
Exercise 9 (e)
• Find a context-free grammar for the following language.
• L = {w ∈ {a, b}* : na(w) ≠ nb(w)}.
8
Section 5.2
Exercise 4
n n
• Find an s-grammar for L = {a b : n ≥ 2}.
9
Section 5.2
Exercise 10
• Give the derivation tree for (a + b) * c + d, using the grammar in Example
5.12.
• E → T | E + T,
• T → F | T * F,
• F → I | (E),
• I → a | b | c.
10
Section 5.2
Exercise 17
• Show that the following grammar is ambiguous.
• S → aSbS | bSaS | λ.
11
Section 6.1
Exercise 6
• Eliminate all useless productions from the grammar
• S → aS | AB | λ,
• A → bA,
• B → AA.
• What language does this grammar generate?
12
Section 6.1
Exercise 8
• Eliminate all λ-productions from
• S → aSSS,
• S → bb | λ.
13
Section 6.1
Exercise 11
• Eliminate all unit-productions from the grammar in Exercise 7.
• S → a | aA | B | C,
• A → aB | λ,
• B → Aa,
• C → cCD,
• D → ddd | Cd.
14
Section 6.2
Exercise 2
• Convert the grammar S → aSb | Sab | ab into Chomsky normal form.
15
Section 6.2
Exercise 10
• Convert the grammar
• S → aSb | bSa | a | b | ab
• into Greibach normal form.
16
Summary
• Remember that the facts we have discovered during the exercises can be
used during the exam, without further proof or evidence.
• You can consider them as agreed or known facts, and start your
arguments from there.
• Solve example or exercise questions by yourself.
• It might look easy if you just follow answers.
• But if you try it by yourself, there might be a few steps you cannot go
forward easily.
17
