1.
Which of the following are true statements about the sizes of various kinds of representations of regular languages?
A.
Every language recognizable by a DFA with n states is recognizable by some NFA with n states
B.
Every language recognizable by an NFA with n states is recognizable by some DFA with n states
C.
Every language describable by a length n regular expression is recognizable by an n state NFA
D.
If two languages A and B are recognized by two (potentially different) DFAs with n states, than the language
A U B can be recognized by a DFA with atmost 2n+1 states
2.
Which of the following statements is incorrect?
A.
The empty string λ belong to all languages
B.
C.
If L is a language containing at least one non empty word then L* is an infinite language
D.
3.
Define FOUR (w), for a finite string w, to be the string consisting of the symbols of w in positions that are multiples of four. For example, FOUR (1110011100) = 01. If L is a regular language, then { FOUR (w) : w є L} must be regular
4.
If L is a language over an alphabet ∑ let NoPrefix(L) = {x є L : no proper prefix of x is in L}. If L is regular then so is NoPrefix(L)
5.
Consider the language defined by the regular expression (a + b)*b^{+}. Which of the following regular expressions also define that language?
6.
Suppose that you have defined an FSA M3 that recognizes {a^{n} | n is divisible by 3}, where M3 has exactly 3 states. Suppose also that you have defined an FSA M2 that recognizes {a^{n} | n is divisible by 2}, where M2 has exactly 2 states. How many states does the machine M2 ∩M3 have?
7.
Which of the following statement is true.
A.
Both the regular languages and the context-free languages are closed under the reverse operation
B.
Neither the regular languages nor the context-free languages is closed under the reverse operation
C.
The regular languages are closed under the reverse operation but the context-free languages are not
D.
The context-free languages are closed under the reverse operation but the regular languages are not
8.
Convert the following DFA into a regular expression
9.
Which of the set can be recognized by DFS automata
A.
The no. 1,2,4,…………….2n,………..written in binary
B.
The set {1, 101, 11011,1110111…}
C.
The no. 1,2,4,……………. ,………..written in unary
D.
The set of binary strings in which the no. of 0’s is same as the no. of 1’s
10.
Minimize the DFA whose transition-function table is given below (the start state is indicated by ↓; an accept state is indicated by *
Which of the following is true?
A.
The minimised DFA has 6 states as 2 ≡ 5 and 4 ≡ 8
B.
C.
The minimised DFA has 5 states
D.
11.
The pumping lemma for regular languages can be used to
A.
Prove that a given language is regular
B.
Prove that a given language is not regular
C.
Prove that all CFL have a corresponding PDA
D.
Prove that a given CFL is inherently ambiguous
12.
Read the following statements
1) For every NFA with an arbitrary no. of the final states there is an equivalent NFA with only one final state
2) Regular sets are closed under infinite union
3) Regular sets are closed under prefix
Which of the following is true?
A.
1 & 3 are only correct statements
B.
1, 2 & 3 statements are correct
C.
1 is the only correct statement
D.
None of the above is correct
13.
The finite state machine described by the following state diagram with A as starting state where an arc label is x/y and x stands for 1-bit input & y stands for 2-bit output.
A.
Output 01 whenever input sequence contains 11
B.
Output 10 whenever input sequence contains 10
C.
Output the sum of the present and previous bits of the input
D.
14.
Which of the following statement is true?
A.
The language { : n >= 0, n !=4} is regular
B.
The set of all real number is a regular language
C.
The language { : n = i+ jk; i, k fixed, j=0,1,2………….} is regular
D.
15.
Let r = 1(1+0)*, s= 11* 0 & t= 1*0 be 3 regular expression as which one of the following is true
16.
How many states are there are in minimized DFA of the following DFA
17.
Which of the following is true
A.
A(ab)*a = a(ba)* & (P*Q*) = (P*+Q*)*
B.
(a+b)*a(a+b)*b(a+b)* = (a+b)*ab(a+b)*
C.
(a+b)*ab[(a+b)*ab(a+b)*+b*a*+b*a*] = (a+b)*
D.
18.
A finite state machine with the following states table has a single input x & single output z. If the initial state is unknown then the shortest input sequence to reach the final state C is
19.
Consider the following FA’s which of the following is true
20.
What is the no. of states in the minimized DFA, which accepts all string whose 8^{th} symbol from right end is ‘1’
21.
The language accepted by push down automaton in which the stack is limited to 10 items is best described as
A.
B.
C.
Deterministic Context free
D.
22.
Which of the following statements are true?
i) The number of outgoing arcs from a state of a DFA is always equal to |Σ|
ii) The number of outgoing arcs from a state of a NFA is always equal to |Σ|
iii) Not all finite languages are regular
iv) The family of regular languages is closed under intersection
23.
Consider the following DFA
The number of states in the equivalent minimized DFA will be
24.
Regular expression corresponding to following FA will be
25.
Which of the following statements are true?
i) If L is regular language, then L^{R} is also a regular language
ii) If L is regular language, then L^{2} may not be a regular language
iii) The grammar {G = ({S}, {a}, S, {S->Saaa | aS| a})} is not regular
iv) The grammar {G = ({S}, {a, b}, S, {S->aS | bS| })} is not regular