“Simpler Notations”.
1.Given Language: L= {xϵ∑= {a, b} |x has a substring ‘aa’ in the production}. Which of the
corresponding representation notate the same?
a)
b)
c)
Answer: a
Explanation: The states transited has been written corresponding to the transitions as per
the row and column. The row represents the transitions made and the ultimate.
2.Let u=’1101’, v=’0001’, then uv=11010001 and vu= 00011101.Using the given information
what is the identity element for the string?
a) u-1
b) v-1
c) u-1v-1
d) ε
Answer: d
Explanation: Identity relation: εw = wε = w, thus the one satisfying the given relation will
be the identity element.
, 3.Which of the following substring will the following notation result?
a) 0101011
b) 0101010
c) 010100
d) 100001
Answer: c
Explanation: The given DFA notation accepts the string of even length and prefix ‘01’.
4.Predict the following step in the given bunch of steps which accepts a strings which is of
even length and has a prefix=’01’
δ (q0, ε) =q0 < δ(q0,0) =δ (δ (q0, ε),0) = δ(q0,0) =q1 < _______________
a) δ (q0, 011) =δ (δ (q0,1), 1) =δ (q2, 1) =q3
b) δ (q0, 01) =δ (δ (q0, 0), 1) = δ (q1, 1) =q2
c) δ (q0, 011) =δ (δ (q01, 1), 1) =δ (q2, 0) =q3
d) δ (q0, 0111) =δ (δ (q0, 011), 0) = δ (q3, 1) =q2
Answer: b
Explanation: Here, δ refers to transition function and results into new state or function
when an transition is performed over its state.
5. Fill the missing blank in the given Transition Table:
Language L= {xϵ∑= {0,1} |x accepts all the binary strings not divisible by 3}
a) Q0
b) Q1
c) Q2
d) No Transition
Answer: b
1.Given Language: L= {xϵ∑= {a, b} |x has a substring ‘aa’ in the production}. Which of the
corresponding representation notate the same?
a)
b)
c)
Answer: a
Explanation: The states transited has been written corresponding to the transitions as per
the row and column. The row represents the transitions made and the ultimate.
2.Let u=’1101’, v=’0001’, then uv=11010001 and vu= 00011101.Using the given information
what is the identity element for the string?
a) u-1
b) v-1
c) u-1v-1
d) ε
Answer: d
Explanation: Identity relation: εw = wε = w, thus the one satisfying the given relation will
be the identity element.
, 3.Which of the following substring will the following notation result?
a) 0101011
b) 0101010
c) 010100
d) 100001
Answer: c
Explanation: The given DFA notation accepts the string of even length and prefix ‘01’.
4.Predict the following step in the given bunch of steps which accepts a strings which is of
even length and has a prefix=’01’
δ (q0, ε) =q0 < δ(q0,0) =δ (δ (q0, ε),0) = δ(q0,0) =q1 < _______________
a) δ (q0, 011) =δ (δ (q0,1), 1) =δ (q2, 1) =q3
b) δ (q0, 01) =δ (δ (q0, 0), 1) = δ (q1, 1) =q2
c) δ (q0, 011) =δ (δ (q01, 1), 1) =δ (q2, 0) =q3
d) δ (q0, 0111) =δ (δ (q0, 011), 0) = δ (q3, 1) =q2
Answer: b
Explanation: Here, δ refers to transition function and results into new state or function
when an transition is performed over its state.
5. Fill the missing blank in the given Transition Table:
Language L= {xϵ∑= {0,1} |x accepts all the binary strings not divisible by 3}
a) Q0
b) Q1
c) Q2
d) No Transition
Answer: b
