Theory of computation assignment help

Theory of Computation TOC | Sample Assignment | www.expertsmind.com

Answer 2a. DFA M=(Q,S,d, q0,F).for any two states q,q’ЄQ,
q≈q’ w єΣ*: δ*(q, w) ó δ*(q’, w)
where δ*(q,e)=q and δ*(q,ax)= δ*( δ(q,a),x)
A relation is ≈ is equivalence if

(i) It is reflexive i.e. x≡x
(ii) It is symmetric ie x≡y => y≡x
(iii) It is transitive ie x≡yΛy≡z =>x≡z

wєΣ δ(q, w) ≡ δ(q’, w)
ó aєΣ xєΣ* : δ*(δ(q, a),x)єF≡ δ*(δ(q’, a),x)єF
ó aєΣ xєΣ* : δ*(q,ax)єF ≡ δ*(q’,ax)єF
ó w’єΣ* : δ*(q,w’)єF ≡ δ*(q’,w’)єF
óq≡q’

2b. state diagram for M=(Q,S,d, q0,F)
0 0,1
0
q0 q1 q2 q3 q4
q1 q4
q0 0 - F - F F
0
1 1 0 1 - - - - F
q3
q2
00 F F F F F
1
01 - F - F F
1
10 - - - - F
[q0] = {q0, q2} 11 - - - - F
[q1] = {q1, q3}
000 F F F F F
[q4] = {q4}
001 F F F F F

010 - F - F F

011 - F - F F

100 F F F F F

101 - - - - F

state diagram for M’
0 0,1
0
q4
q0
q0
0
1 1 0

q2
1

1

4(a) set of all strings that have abba as substring.

b a
a
a,b
a b b a

b

4(b) set of all strings that do not have abba as substring.
b a a
a,b
a b b a

b

b

Theory of computation assignment help

Recommended

Recommended

More Related Content

Viewers also liked

Viewers also liked (6)

More from Expertsmind IT Education Pvt Ltd.

More from Expertsmind IT Education Pvt Ltd. (20)

Recently uploaded

Recently uploaded (20)

Theory of computation assignment help