課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰林智仁
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2010.11.9
考試時限（分鐘）：180+15
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
#Please give details of your calculation. A direct answer without explanation
is not counted.
#Your answers must be in English.
#During the exam you are not allowed to borrow others' class notes.
#Try to work on easier questions first.
Problem 1 (15 pts)
Consider the following DFA:
start→ q1 0→ q2 0→ q3 1→ q4(acc)
↓ ↑ ←1 ↓ ↑ ↓ ↑
1→ 0→ 0,1→
(a)Convert this DFA to a regular expression using GNFA. The order to remove
states must be 1,2,3, and 4.
(b)Try to simplify the obtained regular expression to Σ*001Σ*.
You need to show details.
Problem 2 (15 pts)
We would like to check if
Φ* = {ε}.
(a)Give an NFA for Φ using the smallest number of states.
(b)Following how we construct A* for any given NFA A, give the NFA of Φ*.
(c)Transfer the NFA of Φ* to DFA (using the power set as state sets).
We assume Σ = {0,1}.
(d)Simplify DFA obtained in (c) and give the formal definition of this DFA.
Problem 3 (5 pts)
Give a DFA with five states such that the language is
{0}
We assume Σ = {0,1}. You don't need to give a formal definition
(i.e., a state diagram is enough).
Problem 4 (10 pts)
Is the following language regular?
{xyx^R : x,y belongs to Σ*}
Assume Σ = {0,1}. x^R means the reverse of x.
Problem 5 (10 pts)
If L is regular, is the language
{w | w belongs to L and w^R belongs to L}
regular? We assume Σ = {0,1}. x^R means the reverse of x.
Problem 6 (15 pts)
Is the language
L = {1^k | k belongs to N U {0} but k is not a prime number}
regular? You can assume Σ = {1} and need to show all the details.
Problem 7 (10 pts)
Consider the DFA in Problem 1. Give a CFG for the language of this
DFA. Requirement: #variables≦4, #rules≦9.
Problem 8 (15 pts)
Modify the following CFG to Chomsky normal form:
S → aSb | bY | Ya
Y → bY | aY | ε
Problem 9 (5 pts)
Consider the following PDA. Draw the tree to process the string
0011. Your tree must be complete.
Note that we mean a tree to process an input string.
We don't mean a parse tree of CFG.
←
start → q1(acc) → q2 ↑
ε,ε→$ → 0,ε→0
↓ ε,ε→ε
ε,$ →ε
q4(acc) ← q3 →
←↓ 1,0→ε
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.97