COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
(0+10)*(1+)
|
|
|
(0+10)*(1+)*
|
|
|
(0+101)*(0+)
|
|
|
(1+010)*(1+)
|
Detailed explanation-1: -7. Which of the following represents a language which has no pair of consecutive 1’s if ∑= 0, 1? Explanation: All the options except ‘a’ accept those strings which comprises minimum one pair of 1’s together. Explanation: A finite automaton accepts the languages which are regular and for which a DFA can be constructed.
Detailed explanation-2: -The regular expression (1 + 10)* denotes all strings of 0’s and 1’s beginning with ‘1’ and not having two consecutive 0’s. The regular expression (0 + 1 )* 011 denotes all strings of 0’s and 1 ‘s ending with 011. The regular expression 00(1 +10)* denotes all strings of 0’s and 1’s with atleast two consecutive 0’s.
Detailed explanation-3: -L((0+10)*(+1)) = all strings of 0’s and 1’s without two consecutive 1’s. L((0+1)*101(0+1)*) = all strings of 0’s and 1’s having 101 as a substring.