MCQ IN COMPUTER SCIENCE & ENGINEERING

Previous
Next

COMPUTER SCIENCE AND ENGINEERING

THEORY OF COMPUTATION

Question [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Given languages:i) {anbn|n>=0} ii) <div>n</div>n iii) {w∈{a, b}∗| #a(w)=#b(w)}, # represents occurrences Which of the following is/are non regular?
A
i, iii
B
i
C
iii
D
1. i, ii, iii
Explanation: 

Detailed explanation-1: -Example 3 : DFA with one cycle To find the language it accepts, first from the initial state go to state 1 by reading one a. Then from state 1 go through the cycle 1-2-1 any number of times by reading substring ab any number of times to come back to state 1. This is represented by (ab)*.

Detailed explanation-2: -A language is a regular language if there is a finite automaton that recognizes it. For example, this machine recognizes the language of strings that have an even number of zeroes since any string that has an even number of zeroes will go from the start state to an accepting state.

Detailed explanation-3: -The language accepted by an NFA M is the set of all strings which are accepted by M and is denoted by L (M ). state. For any string w, the nondeterministic automaton can be in a subset ⊆ Q of several possible states. If the final set contains a final state, then the automaton accepts the string.

There is 1 question to complete.
Previous
Next