# MCQ IN COMPUTER SCIENCE & ENGINEERING

## COMPUTER SCIENCE AND ENGINEERING

### THEORY OF COMPUTATION

 Question [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
All the regular languages can have one or more of the following descriptions:i) DFA ii) NFA iii) e-NFA iv) Regular Expressions Which of the following are correct?
 A i, ii, iv B i, ii, iii C i, iv D i, ii, iii, iv
Explanation:

Detailed explanation-1: -Interpret the empty strings e as the number 0. d) None of the mentionedView AnswerAnswer: dExplanation: All of the given languages are regular and finite and thus, can berepresented using respective deterministic finite automata. We can also usemealy ormoore machine to represent remainders for option c.

Detailed explanation-2: -Every regular expression using only *, +, | (but not, say, backreferences) can be converted into a DFA. This is shown in textbooks on formal languages.

Detailed explanation-3: -Non-Deterministic Finite automata (NFA) and Deterministic Finite Automata (DFA) are equal in power that means, every NFA can be converted into its equivalent DFA and vice versa. Hence, statement 1 is true. Every regular language over ∑ can be accepted by a finite automaton. Therefore, both the statement is true.

Detailed explanation-4: -Languages represented by NFAs, DFAs, and regular expressions are called regular languages.

Detailed explanation-5: -Which of the following is a regular language? a)String whose length is a sequence of prime numbersb)String with substring wwrin betweenc)Palindrome stringd)String with even number of Zero’sCorrect answer is option ‘D’.

There is 1 question to complete.