Take Home Exam 1 Solution

Objectives

Reviewing essential concepts of algebra that are extensively used in formal languages theory, this home-work aims to familiarize you with nite automaton (FA), the most restricted abstract computing device to recognize a Regular Language, observing the bene ts and limitations of employing such simplistic the-oretical machinery to tackle practical problems and to help you gain experience in equivalent yet distinct ways of nite representation of the same class of languages such as Regular Expressions.

Speci cations

You must adhere to the notation conventions adapted in the textbook. All automata must be de ned as tuples and you must illustrate state transition functions and state transition relations graphically.

Your solution should be delivered as a .pdf le advisably generated using LATEX. For convenience, a simple code for drawing an automaton is included in the following. On the left-hand side you can see the code segment, and generated automaton is placed on the right.



\ begin { t i k z p i c t u r e }[ shorten >=1 pt , node distance =2 cm , on grid , auto ]

\ node [ state , initial ]  ( q _0)  {$ q _0$};

\ node [ state ] (q _1) [ above right = of q _0] {$ q _1$}; \ node [ state ] (q _2) [ below right = of q _0] {$ q _2$};
\ node [ state , a cc ep t in g ]( q _3)  [ below    right = of  q _1]  {$ q _3$};
\ path [ - >]

    • q _0)  edge  node  {0}  ( q _1) 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 { t i k z p i c t u r e }




0


q1

0
1
start
q0
q3

1
0


q2


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 a ected by the formalization of your solutions.

1

Question 1    (12 pts)

The sets

Ak = fw : w 2 f0; 1g ; jwj    kg

    • = L(0 10(0 [ 1) ) C = 2f0;1g

where k 2 N are given.

Construct formal proofs to state whether the following sets are countable or uncountable. If any of them is countable, you should also show whether they are nite or in nite, i.e. write down their cardinalities in these cases. State any mapping explicitly and give clear references to known theorems if used. Any other assertions must be proven by yourselves so that your concise nal answers are not treated as random guesses.

a.
C n ffxg : x 2 (A280 [ B)g


(3 pts)
b.  A7 \ B \ C


(3 pts)
c.
SC n (A2   B)


(3 pts)
d.
(SC [ Sk1=1 Ak) n f0; 1g
S
n
(3 pts)

(Note that SS = fx : x 2 P for some set P 2 Sg and

k=1 Sk = S1
[ S2 [ ::: Sn.)

Question 2    (13 pts)

All nite automata (FA) with four pre-de ned states on a binary alphabet have de nitions as ve tuples M = (K; ; ; s; F ) such that K = fq0; q1; q2; q3g and = f0; 1g are given, yet other constituents are un xed, i.e. they can take on many distinct values. Assume that two FA are not di erent if and only if all of the associated ve tuples are equal to each other. Pay attention to the distinction between the equivalence of sets and the equivalence of ordered pairs.

a.  How many di erent deterministic FA M exist in accordance with given speci cations?    (5 pts)

    b. How many di erent nondeterministic FA M exist in accordance with given speci cations? (5 pts)

c.  How do you explain the di erence between options (a) and (b)?    (1 pts)

    d. How do the numbers obtained in options (a) and (b) relate to the number of di erent languages

corresponding FA M recognize? Justify your answer in a few sentences.    (2 pts)










2

Question 3    (15 pts)

For each language Li, write a regular expression    i representing the language, i.e.

i 2 f1; 2; 3g . Interpret symbols 0 and 1 as natural numbers in related contexts.

Li = L( i) s.t.
(5 pts)
n
2 f
0; 1
g

i=1


6
2
j
w
j
o
a.
L1 =

w


:
jwj w(i)
is a multiple of 2 and 4, w(i) + w(i + 1) = 2 for i

[1::(


1)] .







P









b.
L2 =nw 2 f0; 1g : jwj is odd, and w(2i) = 0 for i = 1; 2; ::: j
jw2
j
ko.




(5 pts)
c.
L3 =fw 2 f0; 1g : w has even number of interleaved occurrences of the substring 00g.


(5 pts)


(Note: 000 62L3 since it has one interleaved occurrence of 00, yet 0000 2 L3 and 00000 2 L3.)



Question 4    (14 pts)

In each part, construct a deterministic nite automaton (DFA) that recognizes the given language. Draw all your deterministic nite automata (DFA) using graphical notation and write down their con-stituents as ve tuples in set/tuple notation, leaving out the state transition function which must only be depicted graphically. Explicitly draw transitions to trap (dead) states whenever applicable. Interpret symbols 0 and 1 as natural numbers in related contexts.
a.  L1 =nw 2 f0; 1g :
P
ij
=1j
w(i)    2 and
jwj
P
ij
=1j
w(i)    2
o.


w



w













b.  L2 =fw 2 f0; 1g : w contains neither 1011 nor 00 but has 0101 as a substringg.

(7 pts)

(7 pts)


Question 5    (8 pts)

Given the nondeterministic nite automaton (NFA) N=(K, fa; bg, , q0, F ), in which K = fq0; q1; q2; q3; q4g,

= f(q0; b; q1); (q0; e; q2); (q0; b; q3); (q1; a; q1);

(q2; a; q2); (q2; b; q2); (q2; a; q4);

(q3; a; q1); (q3; e; q4);

(q4; a; q1); (q4; a; q2); (q4; b; q4)g

and F = fq1; q3g, trace the following strings on N employing the con guration notation for nondeterministic nite automata (NFA) within yields-in-one-step relation and decide whether they are in L(N) or not utilizing the re exive transitive closure of yields-in-one-step relation. Answers based on reasoning about the type of strings N accepts / rejects will be graded zero.

a.  w1 = abaa.    (4 pts)

b.  w2 = babb.    (4 pts)



3

Question 6    (9 pts)

Given the NFA N=(K, fa; bg,    , q0, F ), in which K = fq0; q1; q2; q3; q4g,

= f(q0; a; q0); (q0; b; q0); (q0; b; q1); (q0; e; q2); (q1; a; q4);

(q2; b; q1); (q2; b; q3); (q3; a; q4)

(q4; e; q3)g

and F = fq3; q4g, construct an equivalent DFA M using the subset construction algorithm for NFA to DFA conversion in the textbook. Precisely show every step of the algorithm applied on N to yield M. Answers comprising of only the resultant DFA M will be graded zero.



Question 7    (9 pts)

Given the NFA N=(K, fa; bg,    , q0, F ), in which K = fq0; q1; q2; q3g,

= f(q0; b; q1); (q0; a; q3); (q1; a; q1); (q1; a; q3);

(q2; a; q2); (q2; b; q2); (q3; b; q1); (q3; b; q2)g
and F = fq2g, construct a regular expression such that L( ) = L(N) using the FA to regular expression conversion method in the textbook. Begin by writing down the generalized nite au-tomaton (GFA) for N. Then, explicitly show every step of the method's application on the GFA. Simplify the obtained regular expression if possible. Answers that do not show interim computations will be graded zero.




Question 8    (10 pts)

Let L be a language over a nite alphabet and assume that f0; 1g is a subset of . De ne another language H as

    • = fw 2   : 0w1 2 Lg:

Show that if L is regular, then so is H. To attain full credit, explicitly construct an FA MH for H, given any FA ML to recognize L; and formally prove that L(MH ) = H.















4

Question 9    (10 pts)

The following language is given.

    • =f1t0m12n : t < 5, m 6= n, and t; m; n 2 Ng. Prove that L is not a regular language by

a.  pumping lemma for regular languages.    (10 pts)

b.  MyHill-Nerode theorem.    (not graded)



Question 10    (not graded)

Decide whether the following languages are regular or not. If you think a language is regular prove your claim by providing a regular expression or FA for it. Otherwise, use MyHill-Nerode theorem or pumping lemma for regular languages to prove that the language is not regular.

    a. L1 = fxy 2 fa; bg : jxj = 2jyj, and x contains the substring aa at indices 3 and 4g

    b. L2 = fxy 2 fa; bg : jxj = 2jyj, and x ends with the substring a and y begins with the substring ag



Question 11    (not graded)

Given DFA M = (K;    ; ; q0; F ), in which K = fq0; q1; q2; q3; q4g,    = f0; 1g,

    • = fq2; q4g, and the state transition function  is tabulated below,

    • (q;  )
q0
0
q1
q0
1
q2
q1
0
q1
q1
1
q3
q2
0
q0
q2
1
q4
q3
0
q1
q3
1
q4
q4
0
q3
q4
1
q2


    a. Apply state minimization algorithm to M to yield an equivalent DFA with minimum number of states.

    b. Write down equivalence classes of partitioned by the DFA with minimal states as regular ex-pressions. For simplicity you may use shorthand notations such as and L s.t. L = L(M) within the regular expressions.





5

List of Acronyms

FA    nite automaton

FA    nite automata

DFA deterministic  nite automaton

DFA deterministic  nite automata

NFA nondeterministic  nite automaton

NFA nondeterministic  nite automata

GFA generalized  nite automaton





Submission

    • You should submit your THE1 as a pdf le with the identi er 'the1.pdf' on odtuclass. You can use the provided .tex template with appropriate modi cations.

    • Soft-copies should be uploaded strictly by the deadline.

    • Late Submission: You have two days in total for late submission with penalties of 20 pts and 50 pts reduction in your grade for the rst and second day, respectively. No further submissions are accepted.

    • Do not submit solutions for not-graded questions. Yet solving them is advisable in studying for the midterm.





Regulations

    1. Cheating: This take-home exam has to be completed and submitted individually. Teaming up, sharing solutions anywhere other parties might access and using work belonging to others as part or in whole are considered cheating. We have zero tolerance policy for cheating. People involved in cheating will be punished in accordance with the university regulations.

    2. Newsgroup: You must follow the newsgroup (cow.ceng.metu.edu.tr) for discussions and possible updates on a daily basis. You are advised to initiate discussions on COW so that most parties will bene t.












6