Test: Regular Expressions & Finite Automata- 4 - Computer Science Engineering (CSE) MCQ

We can generate ε, a, ab, abb, b, aaa, .....

Option A represents those strings which either have 0011 or 1100 as substring. Option C represents those strings which either have 00 or 11 as substring. Option D represents those strings which start with 11 and end with 00 or start with 00 and end with 11.

So, the minimum number of states is 2.   Thus, B is the correct answer.

Statement I : False, Since there is no mention of transition between states. There may be a case, where between two states there is no transition defined.
Statement II: True, Since any empty language (i.e., A = Φ ) is regular and its intersection with any other language is Φ. Thus A ∩ B is regular.

For the acceptance and rejection of any string we can simply check for the movement on each input alphabet between states. A string is accepted if we stop at any final state of the DFA. For string u=abbaba the string ends at t (final state) hence it is accepted by the DFA. For string v=bab the string ends at s (non-final state) and hence rejected by the DFA. For string w=aabb the string ends at s (non-final state) and hence rejected by the DFA. 

The given Language is  Palindrome. A,C and D follow the language but  baba  is not a palindrome  , so B is the answer

By changing grammar, language will not change here. {as converting NFA to DFA language will not be changed}

By looking at option A and D clearly not feasible solution.
Between B and C both contains exactly two 1's but in option B, both 1 will always come together where as in C it is general string.

A state in a DFA is proper subset of states of NFA of corresponding DFA 
=> set of states of NFA =n 
=> no of subsets of a set with n elements = 2ⁿ 
=> m<=2ⁿ

Seemingly, DFA obtained by interchanging final and non-final states will be complement of the given regular language. So, to prove that a family of string is accepted by complement of L, we will in turn prove that it is rejected by L.
(A). Set of all strings that do not end with ab - This statement could be proved right by looking at the b labeled incident edges on the final states and a labeled edges preceding them. Complement of the given DFA will have first two states as final states. First state doesn’t have any b labeled edge that has a labeled edge prior to it. Similarly, second final state doesn’t have any such required b labeled edge. Similarly, it could be proven that all the strings accepted by the given DFA end with ab. Now that L ∪ complement(L) = (a + b) ∗ , L should be the set of all the strings ending on ab and complement(L) should be set of all the strings that do not end with ab. [CORRECT]
(B). Set of all strings that begin with either an a or ab - This statement is incorrect. To prove that we just have to show that a string beginning with a or ab exists, which is accepted by the given DFA. String abaab is accepted by the given DFA, hence it won’t be accepted by its complement. [INCORRECT]
(C). Set of all strings that do not contain the substring ab - To prove this statement wrong, we need to show that a string exists which doesn’t contain the substring ab and is not accepted by current DFA. Hence, it will be accepted by its complement, making this statement wrong. String aba is not accepted by this DFA. [INCORRECT]
(D). The set described by the regular expression b ∗ aa ∗ (ba) ∗ b ∗ - String abaaaba is not accepted by the given DFA, hence accepted by its com

A: Both L₁ and L₂ are CFL 
B: L₁ ∩ L₂ = ∅ is true 
L₁is not regular => true 
=> B is true 
C: L₁ ∪ L₂ is not a CFL nut L₂ is CFL is closed under Union 
=> False 
D: Both L₁ and L₂ accepted by DPDA

1. L 1 is a regular language, as it can be derived by a trivial DFA with 10000 states for each alphabet in the grammar to limit on the number of 0s and 1s to 10000.
2. L 2 is a set of all palindromic strings, which isn’t a regular language because there is no way for a finite automaton to remember which alphabets have occurred.
3. L 3 is a standard regular language as there exists a DFA which can derive this language. You can read more in the references about it.

LR(1) – Reading the input string from left to right. 
LR(1) – Deriving a right-most derivation for the string.
LR(1) – one token look-ahead
In the first choice we read from Left to right deriving the right-most sentential form and looking one symbol ahead which is stack top. So option (a) is correct.

Clearly r1 is a superset of both r2 and r3 as string 1 can not be generated by r2 and r3. r2 is a superset of r3 as string 11 is not present in L(r3) but in L(r2).

For NFA: Just remove the trap state.

First (E’) = {+ ,ԑ} Follow (E’) = {$ , )} 

Therefore 3 entries are present in E’ row

Clearly init (L) = (0+1)*. Take any string in (0+1)* say 101011, we can append required number of symbols to make it a member of L like 10101100.

M2 accepts strings in L(M1) so definitely it will halt. Other 2 are not guaranteed as Turing machine M does not accept w if it either rejects w by halting to a reject state or loops infinitely on w.