Description

THEORY OF COMPUTATION – CS340

CS340 Assignment1

Name: Jaya Gupta
Roll Number: 200471
Name: Harshit Bansal
Prof. Manindra Agarwal
Roll Number: 200428
Name: Avi Bansal
Roll Number: 200229
Q1. Language Accepted by DFA
To find the regular expression for the given DFA, we follow the recursive approach of removing the states one by one, till only start and final states are left.
• Remove q1 and q2: Now q1 is final state and it accepts only set {0}. We can safely remove both theses states as they do not interfere with the rest of DFA.

• Remove q5: New transitions are:

1
• Remove q3:

Hence the language accepted by this DFA is union of those accepted by states q1 and q4.
r = 0 + (1.(0.1∗.0)∗.1).(0 + (1.(0.1∗.0)∗.1)∗)∗
where L(r) is the regular set accepted by DFA.
Q2. If L is regular, oddL is also regular
Q3. Minimum State DFA (Minimization)
1 0
• Remove all the nodes unreachable from the start state. In this question, those nodes are q4,q5,q6, and q7.
• Lets make the transition table for each state.
Transition Table
State 0 1
q0 q1 q0
q1 q0 q2
q2 q3 q1
q3 q3 q0
• Combine all the sinks (i.e. the nodes that can’t reach to final state) into one. Here there are no sinks. We can reach the final state from all the states through some transition.
• Merge non-distinguishable states or states belonging to same equivalence classes whereby every two states of the same equivalence class are equivalent if they have the same behavior for all the input sequences.
• That is, for all states p1,p2 belonging to the same equivalence clas E, the transition taken on reading input w should be equivalent for both – transition to state that both rejects or accepts.
• Divide the states into accepting and rejecting.
R = {q0,q1,q2}
A = {q3}
• Since q0 and q1 on reading 0 or 1 remains in rejecting state, whereas q2 on reading 0 reaches the accepting state. Hence behavior of q2 is different from q0 and q1.
R1 = {q0,q1}
R2 = {q2}
A = {q3}
• q0 on reading 1 remains in R1 only, whereas q1 on reading 1 makes transition to R2. By the definition of equivalence classes, if p and q are two strings in same equivalence class E, so if any extension of p(pw) is in E, then qw will also be in E.
∀p,q ∈ E, pw ∈ E iff qw ∈ E
• q0 and q1 does not follow this property, hence they will be in different equivalence class.
R1 = {q0}
R2 = {q1}
R3 = {q2}
A = {q3}
Hence in the final minimal DFA, there will be four states q0,q1,q2,q3.
Q4. L1 and L2 are regular. Prove Mix(L1,L2) is regular.
Mix(L1,L2) = {w ∈ P∗ |w = x1y1x2y2……xkyk where x1x2….xk ∈ L1 and y1y2……yk ∈ L2, each xi,yi ∈ P∗} We need to show that if L1 and L2 are regular implies that Mix(L1,L2) is also regular.
Construction of DFA of Mix(L1,L2)

• Let F1 and F2 are DFA of L1 and L2 respectively.
F1 = {q01,Q1,X,δ1,F1}
F2 = {q02,Q2,X,δ2,F2} • Let Fm be the NFA of Mix(L1,L2), such that

where
Fm = F1 × F2
δm : δm({q1,q2},a) = {δ1(q1,a),q2}
OR
δm : δm({q1,q2},a) = {q1,δ2(q2,a)}
• Since the transition from a single state {q1,q2} on reading input symbol a can be to two different states, Fm is a NFA.
Proof: Mix(L1,L2) is accepted by Fm

• Inorder to show that Mix(L1,L2) is accepted by NFA, we need to show that there exists at least one transition which accepts Mix(L1,L2).
w=x1y1x2y2……xkyk where x1x2….xk ∈ L1 and y1y2……yk ∈ L2,w ∈ Mix(L1,L2)

Consider the following transition, which is one possible transition in the above NFA Fm

So this transition accepts w.
Note: Here the transition on any input is . Means there are multiple transition involved between any two states. (Shown like that because was unable to show squiggly arrow in DFA diagram).
Proof2: Fm accepts strings which are in Mix(L1,L2) only.

• Let the string accepted by Fm be
w = m1m2m3m4………..mk|mi ∈ X
• Consider two empty strings A and B.
A = ϵ
B = ϵ
• We will concat a alphabet mj in string A if after reading mj, Fm takes transition of the type
δm : δm({q1,q2},a) = {δ1(q1,a),q2}
means, the transition is taken is F1 and the state in F2 remains same.
• We will concat a alphabet mj in string B if after reading mj, Fm takes transition of the type
δm : δm({q1,q2},a) = {q1,δ2(q2,a)}
means, the transition is taken is F2 and the state in F1 remains same.
• Since w is accepted by Fm(final state = F1 × F2), means string A takes F1 to state in F1 (final state), and string B takes F2 to state in F2(final state).
A ∈ L1
B ∈ L2
• Hence this concludes that string w ∈ Mix(L1,L2). It is a mix of string in L1 and L2. Q5. Design NFA
L = {w | w is ababn or aban where n ≥ 0}
NFA accepting above language is:

Note: The transitions not shown for any state for any alphabet are assumed to go into sink.
Q6. Regular or Non-Regular
The strings in language L will have difference between number of 0′s and 1′s equal to 0 or 1. Now consider following strings,
x = 0m1, y = 0m2, where m1, m2 ∈ N and m1 − m2 ≥ 2
Now take w = 1m1. Observe that xw = 0m11m1 will belong in L, whereas yw = 0m21m1 wont belong in L because difference in number of 0′s and 1′s is more than 1. Hence by definition, x and y will belong to different equivalence classes. Also we can generate infinite number of m such that when taken any two at a time, x and y will lie in different equivalence classes. Hence there will be infinite equivalence classes for the given language L, which proves this is not a regular language.
Q7. Convert NFA to DFA.
• Lets make the transition table containing all the states a particular state can reach to on reading a symbol.
Transition Table
State a b c
q0 {q0,q1,q2,q3} {q1,q3} {q1,q3}
q1 {q2} {q2} {q2,q3}
q2 {q3} {q2,q3} {q3}
q3 Sink Sink {q3}
{q1,q3} {q2} {q2} {q2,q3}
{q2,q3} {q3} {q2,q3} {q3}
{q0,q1,q2,q3} {q0,q1,q2,q3} {q1,q2,q3} {q1,q2,q3}
{q1,q2,q3} {q2,q3} {q2,q3} {q2,q3}
• Convert the above transition table into DFA.

Note: All the remaining transitions takes the state to a sink state.
Note: All the remaining states from 2Q are not reachable from the start state. Hence Minimal DFA above does not contain them.
Q8. Let L be the language L = {w ∈ {a,b}∗|w contains equal number of occurences of ab and ba } .
(a) Regular Expression
• The string will be of four types.
– Beginning with a and ending with a. aaa….abbbbb….baaaa….abbb…baaa
– Beginning with a and ending with b. aaa….abbbbb….baaaa….abbb
– Beginning with b and ending with b. bbb….baaaaa…..abbbbb……baaa….abbb
– Beginning with b and ending with a.
bbb….baaa……abbbbb….baaa…….aaa
• The types of string with equal number of occurences of ab and ba will be the strings will be the one starting and ending with the same letter (either a or b). Regualar expression will be
a(a + b)∗a + b(a + b)∗b
(b) DFA /NFA /ϵ−NFA

Note: All the remaining transitions takes the state to a sink state.
Q9. DFA state-minimization
Figure: Minimal DFA
• Remove all the nodes unreachable from the start state. In this question, there are no such nodes.
• Lets make the transition table for each state.
Transition Table
State a b
q1 q2 q3
q2 q4 q1
q3 q1 q5
q4 q6 q4
q5 q5 q6
q6 q6 q6
• Combine all the sinks (i.e. the nodes that can’t reach to final state) into one. Here there are no sinks. We can reach the final state from all the states through some transition.
• Merge non-distinguishable states or states belonging to same equivalence classes whereby every two states of the same equivalence class are equivalent if they have the same behavior for all the input sequences.
• That is, for all states p1,p2 belonging to the same equivalence class E, the transition taken on reading input w should be equivalent for both – transition to state that both rejects or accepts.
• Divide the states into accepting and rejecting.
R = {q1,q2,q3}
A = {q4,q5,q6}
• Since q4,q5,q6 on either reading 0 or 1, remains in the accepting state, they belong to the same equivalence class.
Hence we merge them into one state.

• We can clearly see that the behavior of q1, q2 and q3 are different on reading a or b.
– (q2,q3) : q2 on reading a goes to the final state whereas q3 remains in rejecting state. q3 on reading b goes to final state whereas q2 not. Hence, their behaviors are different.
– (q1,q2) or (q1,q3) : q2 or q3 on reading either a or b goes to the final state, whereas q1 on reading both a and b remains in the rejecting state. Hence behavior of q1 differs from both q2 and q3.
Hence in the final minimal DFA, there will be four states {q1,q2,q3,{q4,q5,q6}}.
Q10. Regular Expression For Reverse
L = {uvvrw | u, v, w ∈ {a,b}+}
The regular expression which has language L is:
r = (a + b)(a + b)∗.(aa + bb).(a + b)∗.(a + b)
The equivalent NFA for above regular expression is:

Q13. Given that language L is regular, is the language such that |x| =
|y|,xy ∈ L} regular? If yes, give a formal proof.
Q15. DFA for no consecutive identical symbols in the string.
L = {s|s ∈ (0,1,2)∗ and {00,11,22} ∈/ substring(s)}