1 Crore+ students have signed up on EduRev. Have you? 
Consider the languages L1 = and L2 = {a}. Which one of the following represents L1 L2^{*} U L1^{*}
Consider the DFA given.
Which of the following are FALSE?
1. Complement of L(A) is contextfree.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2.
Explanation :
(1) L(A) is regular, its complement is also regular and if it is regular it is also context free.
(2) L ( A ) = ( 11*0 + 0 )( 0 + 1 ) * 0*1* = 1*0 ( 0 + 1 ) * Language has all strings where each string contains ‘0’.
(3) A is not minimal, it can be constructed with 2 states
(4) Language has all strings, where each string contains ‘0’. ( atleast length one)
W hat is the complement of the language accepted by the NFA shown below?
The given alphabet contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’. In other words, the NFA accepts a+. Therefore complement of the language accepted by automata is empty string.
Given the language, L = {ab, aa, baa}, which of the following strings are in L*?
1. abaabaaabaa
2. aaaabaaaa
3. baaaaabaaaab
4. baaaaabaa
Hence, the correct answer is option C.
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below
'000' cannot be accepted. So, '00' when gets another 0 must go to a dead state, q.
So, options A and B are eliminated.
By analyzing options C and D, we can understand that when states like 00, 01, 11 or 10 get an input 1 or 0, the next state is the last two digits of the newly formed string.
11 +0 > 110 (So, 11 on 0 goes to 10).
01+1 > 011 (So, 01 on 1 goes to 11).
So option D is correct.
Definition of a language L with alphabet {a} is given as following.
L={ k>0, and n is a positive integer constant}
Q. What is the minimum number of states needed in DFA to recognize L?
For n=3 and k=1,2,3,4,....
it a^3,a^6....so n+1 state
Since n is constant and k is changing but logic is k>0
So n+1 required.
A deterministic finite automation (DFA)D with alphabet {a,b} is given below
Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?
Options (B) and (C) are invalid because they both accept ‘b’ as a string which is not accepted by give DFA. (D) is invalid because it accepts "bba" which are not accepted by given DFA.
Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a nondeterministic finite automaton that accepts L?
We need minimum n+1 states to build NFA that accepts all substrings of a binary string. For example, following NFA accepts all substrings of “010″ and it has 4 states.
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
The regular expression has two 0′s surrounded by (0+1)* which means accepted strings must have at least 2 0′s.
Which one of the following is FALSE?
Deterministic PDA cannot handle languages or grammars with ambiguity, but NDPDA can handle languages with ambiguity and any contextfree grammar. So every nondeterministic PDA can not be converted to an equivalent deterministic PDA.
Given the following state table of an FSM with two states A and B, one input and one output:
Q. If the initial state is A=0, B=0, what is the minimum length of an input string which will take the machine to the state A=0, B=1 with Output = 1?
//(0, 0) 1> (0, 1) 0>(1, 0) 1> (0, 1) and output 1 According to the question we have to reach the states A=0, B=1 and output=1. This state is shown by green color. Thus to reach final states as A=0, B=1 and output=1 we have to reach previous states of A=1, B=0. Since initial states are A=0,B=0 (red); we provide input=1 (to reach A=0,B=1) Now this will give present states as A=0, B=1 and output=0. Now we provide (blue) input=0 (to reach A=1,B=0) with present states as A=0, B=1. The present states will become A=1, B=0 and output=0. This is what is required. On providing input=1 we get final states as A=0, B=1 and output=1. Hence an input string of 3 i.e. 101 leads to the desired output and states.
Which of the following statements is false?
Thus, option (C) is the answer.
Given below are two finite state automata (→ indicates the start state and F indicates a final state)Which of the following represents the product automaton Z×Y?
Solution for the problem is :
Thus, option (A) is correct.
Please comment below if you find anything wrong in the above post.
Match the following NFAs with the regular expressions they correspond to:
1. ϵ + 0(01*1 + 00) * 01*
2. ϵ + 0(10 *1 + 00) * 0
3. ϵ + 0(10 *1 + 10) *1
4. ϵ + 0(10 *1 + 10) *10 *
Trick: Here we see in all the given figures then second state has a loop over the input alphabets. In such cases we should resolve the loop at that state and transform the NFA into a simpler one to get a regular expression for the NFA. For resolving the loop, first reach the state where loop is to be resolved then draw all loops over that state and all possible movements to move to the final state.
Figure P: (when loop resolved at middle state)
Loop at middle state is either by a 00 or a 01*1.
Hence the regular expression: € + 0(00 +01*1)* 01*
Figure Q: (when loop resolved at middle state)
Loop at middle state is either by a 00 or a 10*1.
Hence the regular expression: € + 0(00 +10*1)* 0.
Figure R: (when loop resolved at middle state)
Loop at middle state is either by a 10 or a 10*1.
Hence the regular expression: € + 0(10 +10*1)* 1.
Figure S: (when loop resolved at middle state)
Loop at middle state is either by a 10 or a 10*1.
Hence the regular expression: € + 0(10 +10*1)* 10*. The regular expressions matching with the above gives suitable matching as P1, Q2, R3, S4
Which of the following are regular sets?
I. L = {a n b 2m m, n ≥ 0} is a regular language of the form a ∗ (bb) ∗ .
II. L = {a n b m n = 2m} is not a regular language. This is a similar language as of {a n b n} which is known to be not a regular language.
III. L = {a n b m n notEqualTo m} is not regular because there is no way to for finite automaton to remember n, number of as.
IV. L = {xcyx, y ∈ {a, b} ∗} is a regular language which is concatenation of {xx ∈ a, b ∗ } on itself with a alphabet c in between.
Note: Regular languages are closed under concatenation. Hence, correct answer would be (A) I and IV only.
Some points for Regular Sets:
Option A: Every subset of a regular set is regular is False. For input alphabets a and b, a*b* is regular. A DFA can be drawn for a*b* but a n b n for n≥0 which is a subset of a*b* is not regular as we cannot define a DFA for it.
Option B: Every finite subset of a nonregular set is regular is True. Each and every set which is finite can have a welldefined DFA for it so whether it is a subset of a regular set or nonregular set it is always regular.
Option C: The union of two nonregular sets is not regular is False. For input alphabets a and b, a^{n} b^{n} for all n≥0 is nonregular as well as a^{n} b^{m} for n≠m is also non regular but their union is a*b* which is regular.
Option D: TInfinite union of finite sets is regular is False. For input alphabets a and b sets {ab}, {aabb}, {aaabbb}…….. are regular but their union {ab} U {aabb} U {aaabbb} U …………………….. gives {a n b n for n>0} which is not regular.
A minimum state deterministic finite automaton accepting the language L={w  w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has
Hence 3 * 5 states, i.e. there will be 15 states in the automaton to represent this.
Which of the following languages is regular?
(C) Strings which are the part of this language are either 0w0 or 1w1 where w is any string in {0, 1}*. Thus, the language given in option (C) is regular.
All other languages accept strings that have a palindrome as their substring.
(A) Strings intersect with 0*110* .
(B) Strings intersect with 0*110*1 .
(D) Strings intersect with 10*110* .
According to the pumping lemma, languages given options (A), (B) and (D) are irregular.
Thus, option (C) is the answer.
Consider the following Finite State Automaton:
The language accepted by this automaton is given by the regular expression
Thus, C is the correct choice.
Consider the automata given in previous question. The minimum state automaton equivalent to the above FSA has the following number of states
Following is equivalent FSA with 2 states.
136 docs165 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
136 docs165 tests









