Test: Regular Expressions & Finite Automata- 4

# Test: Regular Expressions & Finite Automata- 4

Test Description

## 20 Questions MCQ Test RRB JE for Computer Science Engineering | Test: Regular Expressions & Finite Automata- 4

Test: Regular Expressions & Finite Automata- 4 for Computer Science Engineering (CSE) 2022 is part of RRB JE for Computer Science Engineering preparation. The Test: Regular Expressions & Finite Automata- 4 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Regular Expressions & Finite Automata- 4 MCQs are made for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Regular Expressions & Finite Automata- 4 below.
Solutions of Test: Regular Expressions & Finite Automata- 4 questions in English are available as part of our RRB JE for Computer Science Engineering for Computer Science Engineering (CSE) & Test: Regular Expressions & Finite Automata- 4 solutions in Hindi for RRB JE for Computer Science Engineering course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Regular Expressions & Finite Automata- 4 | 20 questions in 60 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study RRB JE for Computer Science Engineering for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
 1 Crore+ students have signed up on EduRev. Have you?
Test: Regular Expressions & Finite Automata- 4 - Question 1

### Which of the following languages is generated by the given grammar? S -> aS|bS|ε

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 1

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

Test: Regular Expressions & Finite Automata- 4 - Question 2

### Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 2

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.

Test: Regular Expressions & Finite Automata- 4 - Question 3

### The number of states in the minimum sized DFA that accepts the language defined by the regular expression (0+1)*(0+1)(0+1)* is __________________ [Note that this question was originally asked as Fill-in-the-Blanks type]

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 3

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

Test: Regular Expressions & Finite Automata- 4 - Question 4

Consider the following two statements:

I. If all states of an NFA are accepting states then the language accepted by the NFA is Σ∗ .
II. There exists a regular language A such that for all languages B, A ∩ B is regular.

Q. Which one of the following is CORRECT?

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 4

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.

Test: Regular Expressions & Finite Automata- 4 - Question 5

In the automaton below, s is the start state and t is the only final state.

Consider the strings u = abbaba, v = bab, and w = aabb. Which of the following statements is true?

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 5

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.

Test: Regular Expressions & Finite Automata- 4 - Question 6

In the context-free grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string S → aSa | bSb | a | b | ϵ Which of the following strings is NOT generated by the grammar?

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 6

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

Test: Regular Expressions & Finite Automata- 4 - Question 7

Which regular expression best describes the language accepted by the non-deterministic automaton below?

Test: Regular Expressions & Finite Automata- 4 - Question 8

Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ?

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 8

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

Test: Regular Expressions & Finite Automata- 4 - Question 9

Which of the following regular expressions describes the language over {0, 1} consisting of strings that contain exactly two 1's?

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 9

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.

Test: Regular Expressions & Finite Automata- 4 - Question 10

Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 10

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 = 2n
=> m<=2n

Test: Regular Expressions & Finite Automata- 4 - Question 11

If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA?

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 11

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

Test: Regular Expressions & Finite Automata- 4 - Question 12

Consider the following languages.

L1 = {ai bj ck | i = j, k ≥ 1}
L1 = {ai bj | j = 2i, i ≥ 0}

Q. Which of the following is true?

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 12

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

Test: Regular Expressions & Finite Automata- 4 - Question 13

Which of the following languages is (are) non-regular? L1 = {0m1n | 0 ≤ m ≤ n ≤ 10000} L2 = {w | w reads the same forward and backward} L3 = {w ∊ {0, 1} * | w contains an even number of 0's and an even number of 1's}

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 13

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.

Test: Regular Expressions & Finite Automata- 4 - Question 14

Consider the following two finite automata. M1 accepts L1 and M2 accepts L2.

Q. Which one of the following is TRUE?

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 14

Test: Regular Expressions & Finite Automata- 4 - Question 15

Which of the following intuitive definition is true about LR(1) Grammar.

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 15

LR(1) – Reading the input string from left to right.
LR(1) – Deriving a right-most derivation for the string.
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.

Test: Regular Expressions & Finite Automata- 4 - Question 16

Consider the Following regular expressions

r1 = 1(0 + 1)*
r2 = 1(1 + 0)+
r3 = 11*0

Q. What is the relation between the languages generated by the regular expressions above ?

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 16

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).

Test: Regular Expressions & Finite Automata- 4 - Question 17

Consider regular expression r, where r = (11 + 111)* over Ʃ = {0, 1}. Number of states in minimal NFA and DFA respectively are:

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 17

For NFA: Just remove the trap state.

Test: Regular Expressions & Finite Automata- 4 - Question 18

Consider the grammar G.

E -> TE’
E’ -> +TE’ | ԑ
T’ -> FT’
T’ -> *FT’ | ԑ
F -> (E) | id

If LL(1) parsing table is constructed using the grammar G, then how many entries are present in the row that represents E’ nonterminal ? (consider the entries which are not error/not blank entries)

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 18

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

Therefore 3 entries are present in E’ row

Test: Regular Expressions & Finite Automata- 4 - Question 19

Let, init (L) = {set of all prefixes of L},
Let L = {w | w has equal number of 0’s and 1’s}
init (L) will contain:

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 19

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.

Test: Regular Expressions & Finite Automata- 4 - Question 20

Suppose M1 and M2 are two TM’s such that L(M1) = L(M2). Then

Detailed Solution for Test: Regular Expressions & Finite Automata- 4 - Question 20

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.

## RRB JE for Computer Science Engineering

3 videos|7 docs|100 tests
 Use Code STAYHOME200 and get INR 200 additional OFF Use Coupon Code
Information about Test: Regular Expressions & Finite Automata- 4 Page
In this test you can find the Exam questions for Test: Regular Expressions & Finite Automata- 4 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Regular Expressions & Finite Automata- 4, EduRev gives you an ample number of Online tests for practice

## RRB JE for Computer Science Engineering

3 videos|7 docs|100 tests