CISB353-assignment02
- 格式：docx
- 大小：41.65 KB
- 文档页数：2
CISB353 Formal Languages and Automata
1 st Semester 2015/2016
Assignment 2
Due: Monday September 21st, 2015
Lao Kuok Long
D-B2-2736-5
Q1.
Write a regular expression to denote a language 𝐿 over Σ ∗ , where Σ = {𝑎, 𝑏, 𝑐} such
that every string contains the substring ‘abcc’.
Ans:
(a + b + c)*abcc(a + b + c)*
Q2.
Write a regular expression to denote a language 𝐿 over Σ ∗ , where Σ = {𝑎, 𝑏} such
that the third character from the right end of the string is always ‘a’.
Ans:
(a + b)*a(a + b)(a + b)
Q3.
Write a regular expression to denote a language 𝐿 over Σ ∗ , where Σ = {0, 1} such
that every string does not contain two consecutive 1’s.
Ans:
(10 + 0)*(1 + 𝜀)
Q4.
Write a regular expression to denote a language 𝐿 over Σ ∗ , where Σ = {𝑎, 𝑏} such
that every string contains an odd number of b’s.
Ans:
(a*ba*b)*a*ba*
Q5.
Construct an𝜀-NFA for the following regular expression.
1 + (0 + 1) *1*
Ans:
Q6.
Construct an𝜀-NFA for the language having an odd number of one’s over the set Σ =
{1}.
Ans:
RE is 1(1 1)*
𝜀-NFA of the regular expression
Q7.
Ans:
a(aa)*b + ab*a
Q8.
Ans: a(a + b)*
