MCQ IN COMPUTER SCIENCE & ENGINEERING

COMPUTER SCIENCE AND ENGINEERING

THEORY OF COMPUTATION

Question [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Which among the following is equivalent to the given regular expression? 01*+1
A
(01)*+1
B
0((1)*+1)
C
(0(1)*)+1
D
((0*1)1*)*
Explanation: 

Detailed explanation-1: -To answer your question, no. They are not the same.

Detailed explanation-2: -Regular Expression: (0+10)*(+1) – L((0+10)*(+1)) = all strings of 0’s and 1’s without two consecutive 1’s. Regular Expression: (0+1)(0+1) – L((0+1)(0+1) ) = 00, 01, 10, 11 = all strings of 0’s and 1’s of length 2. For every regular expression there is a finite automaton.

Detailed explanation-3: -Which of the following regular expression is equivalent to R(1, 0)? Explanation: What we observe from the question is that, it includes e and 11 and any number of 1’s then. Therefore, its simplifies when we write the same reg. Expression as (11+111)*.

Detailed explanation-4: -In the notation 0, 1*, set notation 0, 1 is used to denote “0 or 1". Alternatively, + is also used to denote alternation (JFLAP, for example). So (0+1) can also mean “0 or 1". | is also used to denote alternation (0|1) in theoretical computer science context.

There is 1 question to complete.