Description

CENG280
Formal Languages and Abstract Machines
Take Home Exam 1

Objectives
To familiarize with computation using the Finite Automata, the most restricted formal computational device, observing the benefits and limitations of employing such simplistic theoretical devices to tackle practical problems.
Specifications
You must adhere to the notation conventions adopted in the textbook. All finite automata must be defined as tuples and you must illustrate state transition functions and state transition relations graphically.
Your solution should be delivered as a .tex file based on your modification of the provided template file. For convenience, a simple code for drawing an automaton is included in the following. On the lefthand side you can see the code segment, and generated automaton is placed on the right.
0
egin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
ode[state,initial] (q_0) {$q_0$};
ode[state] (q_1) [above right=of q_0] {$q_1$};
ode[state] (q_2) [below right=of q_0] {$q_2$};
ode[state,accepting](q_3) [below right=of q_1] {$q_3$};
path[->]
(q_0) edge node {0} (q_1) start edge node [swap] {1} (q_2) (q_1) edge node {1} (q_3) edge [loop above] node {0} () (q_2) edge node [swap] {0} (q_3) edge [loop below] node {1} ();
end{tikzpicture}
1
Questions and submission regulations are included in subsequent sections. Designing your solutions to the tasks, explicitly state any assumptions you make and pay particular attention to the notation you use. Your proofs must be sound and complete. Grading will be heavily affected by the formalization of your solutions.
Question 1 (15 pts)
Give formal proofs to state whether the following sets are finite or infinite, and countable or uncountable. State any mapping explicitly and give clear references to known theorems if used.
a. The set of rational numbers inside the open interval (−1, 0).
b. The set D = {L+ : L is a finite language over the unary alphabet Σ = {a} and L+ is not regular.}.
c. The set of all languages on the binary alphabet Σ = {a,b} which cannot be recognized by any Finite Automaton.
Question 2 (15 pts)
In each part, draw the state diagram of a DFA that accepts the given language.
a. L1 ={w ∈ {a,b}∗ : neither abb nor ba is a substring of w}.
b. L2 ={w ∈ {a,b}∗ : w comprises of even length of characters and every third letter is b}.
c. L3 ={w ∈ {a,b,c}∗ : every a is directly preceeded by c and followed by b}.
Question 3 (12 pts)
Given NFA N=(K, Σ, ∆, q0, F), in which K = {q0,q1,q2,q3,q4,q5}, Σ = {a,b},
∆ = {(q0,a,q1),(q0,e,q2),
(q1,e,q2),(q1,e,q3),
(q2,a,q2),(q2,a,q4),
(q3,a,q1),(q3,a,q2),(q3,a,q5),(q3,b,q3),(q3,b,q4),
(q4,a,q5),(q4,b,q3),
(q5,e,q1)} and F = {q5}, trace the following strings on N employing formal NFA configuration notation and decide whether they are in L(N) or not.
a. w1 = abbb.
b. w2 = ababa.
Question 4 (15 pts)
Given NFA N=(K, Σ, ∆, q0, F), in which K = {q0,q1,q2,q3}, Σ = {a,b}, F = {q2,q3}, and
∆ = {(q0,b,q1),
(q1,a,q2),(q1,e,q3),
(q2,a,q0),(q2,b,q1),(q2,b,q2),(q2,b,q3),
(q3,b,q1),(q3,a,q3)},
a. Formally specify and draw the generalized finite automaton (GFA) for N.
b. Step-by-step convert the GFA into a regular expression via state elimination.
Question 5 (18 pts)
Given NFA N=(K, Σ, ∆, q0, F), in which K = {q0,q1,q2,q3}, Σ = {a,b}, F = {q3}, and
∆ = {(q0,a,q1),(q0,e,q1),(q0,b,q2),
(q0,e,q2),(q2,a,q3),(q3,b,q1),(q3,e,q1)},
a. Use subset construction algorithm to find an equivalent DFA M s.t. L(M) = L(N).
b. Express the language L¯ where L = L(N) as a regular expression. State what property L¯ has using set notation.
Question 6 (15 pts)
Prove that the class of regular languages is closed under set difference operation by explicitly constructing an NFA for the language L1 − L2 for any two arbitrary regular languages L1 and L2. Be very clear, formally showing every step of NFA construction. Mind that just writing that regular languages are closed under some operation will not be accepted as a correct answer. You should give an algorithm for the construction of the required NFA, taking inputs as FA to recognize L1 and L2.
Question 7 (10 pts)
Given the following language
L ={w ∈ {a,b}∗ : f(a,w) = n2 for some n ∈ N}
in which f is a function defined as Σ × Σ∗ → N where Σ is a finite alphabet, returning the number of occurrences of its first parameter within its second parameter.
Prove that L is not a regular language by
a. pumping lemma for regular languages.
Question 8 (not graded)
Decide whether the following languages are regular. If you think a language is regular prove your claim by providing a regular expression for it. Otherwise use MyHill-Nerode theorem to prove that the language is not regular.
a. L1 = {xy ∈ {a,b}∗ : |x| = |y| and y ends with the substring aa}.
b. L2 = {xy ∈ {a,b}∗ : |x| = |y| and x contains the substring aa}.
Question 9 (not graded)
Given DFA M = (K,Σ,δ,q0,F), in which K = {q0,q1,q2,q3,q4}, Σ = {0,1},
F = {q2,q4}, and the state transition function σ is tabulated below,

a. Apply state minimization algorithm to M to yield an equivalent DFA with minimal states.
Submission
• You should submit your THE1 as a .tex file. Please use the template provided on COW with appropriate modifications.
• Do not submit solutions for not-graded questions. Yet solving them is advisable in studying for the midterm.
Regulations
2. Newsgroup: You must follow the newsgroup (news.ceng.metu.edu.tr) for discussions and possible updates on a daily basis.