# Toc Online Test Quiz

25 Questions | Total Attempts: 1070  Settings  .

Questions and Answers
• 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.

λ ε {a*}

• 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
• A.

True

• B.

False

• C.

Can't say

• D.

None of these

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

True

• B.

False

• C.

Can't Say

• D.

None of these

• 5.
Consider the language defined by the regular expression (a + b)*b+. Which of the following regular expressions also define that language?
• A.

(a*b+) + (b*b+)

• B.

(ab + bb)* b*

• C.

(a + b + ba)*b+

• D.

Both a and c

• 6.
Suppose that you have defined an FSA M3 that recognizes {an | n is divisible by 3}, where M3 has exactly 3 states. Suppose also that you have defined an FSA M2 that recognizes {an | 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
• A.

0*10*1 (0 U 10*10*1)*

• B.

10* (0 U 10*10*1)* 10*

• C.

(0 U 10*10*1)* 0*10*1

• D.

None of the above

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

2 ≡ 5 ≡ 7.

• C.

The minimised DFA has 5 states

• D.

None

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

None of the above

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

All of the above

• 15.
Let r = 1(1+0)*, s= 11* 0 & t= 1*0 be 3 regular expression as which one of the following is true
• A.

L(s) L(r) & L(s)  L (t)

• B.

L(r)  L(s) & L(s) L (t)

• C.

L (t) L(s) & L(r)  L(s)

• D.

L (t) L(s) & L(s)  L(r)

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

None of the above

• 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
• A.

01

• B.

10

• C.

110

• D.

101

• 19.
Consider the following FA’s which of the following is true
• A.

FA1 FA2

• B.

FA2  FA1

• C.

FA1 = FA2

• D.

None of the above

• 20.
What is the no. of states in the minimized DFA, which accepts all string whose 8th 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.

Context Free

• B.

Regular

• C.

Deterministic Context free

• D.

Recursive

• 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
• A.

I and iv

• B.

I, ii and iv only

• C.

Ii, iii and iv only

• D.

All of the above

• 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
• A.

(ab + aaa*b)*(a+ )

• B.

(ab + aaa*b)*

• C.

(a + aaa*b)* (a+ )

• D.

None of the above

• 25.
Which of the following statements are true? i)        If L is regular language, then LR is also a regular language ii)      If L is regular language, then L2 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
• A.

I only

• B.

I and iii and iv only

• C.

Ii, iii and iv only

• D.

Iii and iv only

Related Topics