课程名称︰自动机与形式语言
课程性质︰大三必修
课程教师︰陈伟松
开课学院：电机资讯学院
开课系所︰资讯工程学系
考试日期（年月日）︰2018/11/05
考试时限（分钟）：180分钟
试题 :
Instructions
- This is a closed book exam.
- Write down your name and student number clearly.
- Write down your solutions clearly.
- There are FIVE questions altogether.
- Discussions/collaborations are NOT allowed.
- All electronic devices must be switched off during the exam.
- You don't need to do the questions in the same order as written here.
- You can use any result discussed, or stated in the class or in the
homework.
- However, if you use results never stated in the class or in the homework
before, you must supply their complete proofs.
- You can also freely use pumping lemma (for both regular languages and
CFL).
In the following, the alphabet is always Σ = {a, b}.
Question 1. [2 points] Construct the NFA/regex for each of the following
languages.
2n
(a) L = {a | n ≧ 1ｽ.
1
(b) L = {w | every a in w is followed immediately by b}.
2
(c) L = {w | w contains three consecutive a's}.
3
(d) L = {w | w does not contain three consecutive a's}.
4
You don't need to prove your NFA/regex is correct, but too complicated
solutions will be considered wrong.
Sample Solution:
(a) L is defined by the regex aa(aa)*.
1
(b) L is accepted by the following DFA:
2
ｂ ａ
╭╮ ╭╮
│↓ ａ │↓
╔═╗─────→┌─┐
→║ ║ │ │
╚═╝←─────└─┘
ａ
(c) L is defined by the regex Σ*aaaΣ*.
3
Alternatively, one can also construct the following DFA:
ｂ ａ
╭╮ ╭╮
│↓ ｂ ａ │↓
┌─┐←──────────┌─┐────→╔═╗
→│ │ ａ ａ │ │ ║ ║
└─┘───→┌─┐───→└─┘ ╚═╝
↑ │ │ ↑│
╰─────└─┘ ╰╯
ｂ ｂ
(d) L is accepted by the complement of the DFA in (c).
4
Question 2. [2 points] Prove or disprove the following for every regular
expressions r and s.
(a) L(r*∪s*) = L((r∪s)*).
(b) L((r*‧s*)*) = L((r‧s)*).
(c) L((r*∪s)*) = L((r∪s)*).
(d) L((r*∪s*)*) = L((r∪s)*).
Sample Solution:
Abusing the notation, for two regex e and e', we write e = e' to denote
L(e) = L(e'). Likewise, e ⊆ e' denotes L(e) ⊆ L(e') and e ≠ e' denotes
L(e) ≠ L(e').
(a) r*∪s* ≠ (r∪s)*, when r = a and s = b.
(b) (r*‧s*)* ≠ (r‧s)*, when r = a and s = b.
(c) (r*∪s)* = (r∪s)*.
Proof. Note that r∪s ⊆ r*∪s, hence, (r∪s)* ⊆ (r*∪s)*. The other
direction follows from the following.
(r*∪s)* ⊆ ((r∪s)*∪s)* = ((r∪s)*)* = (r∪s)*
The inclusion comes from the face that r ⊆ r∪s, and hence, r* ⊆ (r∪s)*.
The first equality comes from the fact that s ⊆ (r∪s)*, and hence,
(r∪s)*∪s = s, whereas the second equality from the fact that (A*)* = A*,
for every set A.
(d) (r*∪s*)* = (r∪s)*.
Proof. Applying the equality in (c), we have the following.
(r∪s)* = (r*∪s)* = (r*∪s*)*.
Question 3. [2 points] Construct the CFG for the following languages.
n n
(a) K = {a b | n ≧ 1}.
1
n n
(b) K = {a xb | x ∈ Σ* and n ≧ 1}.
2
n n m m
(c) K = {a b a b | n, m ≧ 1}.
3
n m n m
(d) K = {a a b b | m, n ≧ 1}.
4
You don't need to prove your CFG is correct, but too complicated grammars will
be considered wrong.
Sample Solution:
(a) K is generated by the following grammar:
1
S → aSb | ab
(b) K is generated by the following grammar:
2
S → aSb | X
X → aX | bX |ε
(c) K is generated by the following grammar:
3
S → XX
X → aXb | ab
(d) K is generated by the following grammar:
4
S → aSb | X
X → bXa | ba
Question 4. [2 points] A grammar ｇ =〈Σ, V, R, S〉is called left-linear, if
each of its rule in R is in one of the following forms:
A → aB,
A → a,
where A, B are variables and a is a terminal. That is, on the right hand side
of a rule, there is one terminal and at most one variable. Moreover, if a
variable appears, ir appears at the end. A language L is called left-linear,
if it can be generated by a left-linear grammar. Prove that every left-linear
language is regular.
Sample Solution:
Let ｇ =〈Σ, V, R, S〉be a left-linear grammar. Construct the following NFA
Ａ =〈Σ, Q, q , F, δ〉, where the set of states Q is V∪{q }, the initial
0 f
state q is S, the set of final states is F = {q }, and the set of transitions
0 f
δ is as follows.
- For every rule A → cB in R, we have a transition (A, c, B) in δ.
- For every rule A → c in R, we have a transition (A, c, q ) in δ.
f
show that L(ｇ) = L(Ａ) holds, we can prove that for every word w, for every
variable A, the following holds.
- S ═>* wA if and only if there is a run of Ａ from S to A on w.
- S ═>* w if and only if there is a run of Ａ from S to q on w.
f
The proof is straightforward induction on the length of w.
Question 5. [2 points] Prove that if L is regular and K is CFL, then L∩K is
CFL.
Sample Solution:
Let Ａ =〈Σ,Γ, Q , q , F , δ 〉be a PDA that accepts K and Ａ =〈Σ, Q ,
1 1 0,1 1 1 2 2
q , F , δ 〉 be an NFA that accepts L.
0,2 2 2
Construct the following PDA Ａ = 〈Σ,Γ, Q, q , F, δ〉that simulates both Ａ
0 1
and Ａ simultaneously.
2
- Q = Q ×Q .
1 2
- q = (q , q ).
0 0,1 0,2
- F = F ×F .
1 2
- δ is defined as follows.
- For every (p , x, pop(y) → (q , push(z)) ∈ δ , where x ≠ε and
1 1 1
(p , x, q ) ∈ δ , the following transition is in δ:
2 2 2
((p , p ), x, pop(y) → (q , q ), push(z))
1 2 1 2
- For every (p , x, pop(y) → (q , push(z)) ∈ δ , where x = ε, for
1 1 1
every p ∈ Q , the following transition is in δ:
2 2
((p , p ), x, pop(y) → (q , p ), push(z))
1 2 1 2
That Ａ accepts precisely L(Ａ ) ∩ L(Ａ ) can be proved in a similar manner as
1 2
the fact that regular languages are closed under intersection.