Answer To: screen-shot XXXXXXXXXXat XXXXXXXXXX5scg2kqu.png screen-shot XXXXXXXXXXat XXXXXXXXXXenwhlvu0.png...
Swapnil answered on Aug 16 2021
1
Circle T for true an d F for false for each the following statements.
a
The language of the regular expression (0*1*)*000(0U1)* consists of all strings of )’s and 1’s with exactly one substring of three consecutive )’s.
T
b
There exist context-free grammars that produce languages that are not regular.
F
C
The empty string equals the empty set.
T
D
If language L is Turing-recognizable but not decidable, then L must not be Turing-recognizable.
F
E
If there exists a reduction from language L to the language ATM then L is not Turing-recognizable.
F
F
If A<=m B and A is decidable, then B is decidable,
T
G
If A<=p B, then A<=m B.
T
H
If there exists a NTM M that solves CLIQUE in polynomial time, then P = NP.
F
I
All intractable problems are decidable.
T
J
SAT polynomial time reduces to every language L in the class NP.
T
2
Consider the finite automata M = (Q, , Σ, δ, q0, {q0, q3}), with d-transitions d(q0, a) = q1, d(q1,b) = q1, d(q1,c) = q2, d(q2,a) = q3, d(q2,b) = q2, and d(q2, c) = q2.
A
What is L(M)?
M = (Q, Σ, δ, q0, {q0, q3}), where:
Q = {q0, q1, q2, q3}
Σ = {a, b}
δ = {(q0, a, q2),
(q0, b, q1),
(q1, a, q2),
(q1, b, q3),
(q2, a, q2),
(q2, b, q1),
(q3, a, q2),
(q3, b, q3)}
L(M) = {q3}
B
Is L(M) finite? Justify.
M = {q0, q1, q2, q3}
Σ = {a, b}
δ = {(q0, a, q1),
(q0, b, q3),
(q1, a, q3),
(q1, b, q2),
(q2, a, q0),
(q2, b, q3),
(q3, a, q3),
(q3, b, q3)}
L(M) = {q2}
C
Is M a DFA? Justify.
3
Let D = {w|w contains even number of a’s and an odd number of b’s and no substring ab}. Design a DFA with five states that recognizes D.
Consider the language D = {w|w contains an even number of a’s and an odd number of b’s and does not contain the substring ab}.
The language D can be described simply as follows D={w|w contains an odd number of b’s followed by even number of a’s}.
Let M be the DFA with five states that recognizes the language D. The state diagram of M is as follows:
The language accepts the strings like {b,baa, bbbaaa,….}. The string b is accepted by the language because, it contains the odd number of b’s (1) followed by even number of a’s (0).
Now, the language D can be expressed as combination of following two languages D1 ans D2.
D1 = {w|w contains odd number of b’s}
D2 = {w|w contains odd number of a’a
D = D1oD2
R1 be the regular expression...