Free Printable TOC Gate questions SET-2

1.

Obtaining the final string by concatenating the labels of the tree from left to right is called yield of a _____ tree.

a)

Perfect

b)

Concatenation

c)

Leaves crafting

d)

Parse

2.

Given the grammar G = {{S, B}, {0,1}, {S}, P}, what are {0,1}?

a)

Non terminals

b)

Production

c)

Starting Symbol

d)

Terminals

3.

What is an approach in CFG that starts derivation from the tree leaves?

a)

Bottom-down approach

b)

Top-up Approach

c)

Bottom-less Approach

d)

Bottom-up Approach

4.

Which among the two approaches reduces an input string back to the start symbol?

a)

Top down

b)

Bottom up

5.

What is an approach that draws the derivation tree from the start symbol to the tree leaves?

a)

Topping approach

b)

Top gearing approach

c)

Top down approach

d)

Derivation down approach

6.

A (a) form is a tree wherein if the partial derivation tree contains the root vertex.

7.

What is a type of derivation tree that is obtained by applying production to the rightmost variable in each step?

a)

Right part tree

b)

Right derivation tree

c)

Production processing rightly

d)

Rightly derivation tree

8.

A left recursive production has a form of X --> aX. True or False

a)

True

b)

False

9.

A grammar G is said to be ________ if there exists two or more derivation tree for some sting in a L(G).

a)

Ambitions

b)

Ambigious

c)

Ambiguous

d)

Ambitious

10.

The set of all CFL is identical to the set of languages accepted by (a) Automata.

11.

Which of the following is NOT considered closed for Context free languages?

a)

Concatenation

b)

Union

c)

Kleen Star

d)

Complement

12.

During the derivation of a tree, if the leaves are null, then the derivation is null. True or False

a)

True

b)

False

13.

Which of the following is not a Context-Free Grammar ?

a)

$a^nb^{4m}$ Where mn $\ge$ 1

b)

$a^ib^j$ Where mn $i\ne2j+1$

c)

$a^{n^n}$ Where n $\ge$ 1

d)

$a^mb^{m+n_{ }}c^n$ Where mn $\ge$ 1

14.

Which of the following RE are equivalent?

1. (00)* 2. (00)* ( $\epsilon$ +o)*

3. 0* 4. 0(00)*

a)

1 and 2

b)

2 and 3

c)

2 and 4

d)

3 and 4

15.

How many states does Minimum DFA needs to construct a language where all string ending with "ab"

a)

2

b)

3

c)

4

d)

5

16.

Which of the following statement is TRUE for language L ?

a)

L is acceptable by Turing machine than it is not acceptable by PDA

b)

L is acceptable by PDA than it is not acceptable by turning machine

c)

L is acceptable by RE than it is not acceptable by CFG

d)

L is accoetable by RG and CFG, cannot be acceptable by turning machine

17.

Which of the following statement is TRUE for language L ?

a)

L is acceptable by Turing machine than it is not acceptable by PDA

b)

L is acceptable by PDA than it is not acceptable by turning machine

c)

L is acceptable by RE than it is not acceptable by CFG

d)

L is accoetable by RG and CFG, cannot be acceptable by turning machine

18.

$D_p$ $N_p$ $D_f$ $N_f$ are PDA, NPDA, DFA and NFA,respectively.

Which of the following statement is correct ?

a)

$D_p$ = $N_p$

b)

$D_f$ = $D_p$

c)

$D_f$ = $N_f$

d)

$N_p$ = $N_f$

19.

RE= (01+11)*

How many states need to design a minimum DFA?

a)

2

b)

3

c)

1

d)

4

20.

Identify the language generated by the grammar

S-->XY

X-->aX/a

Y-->bY/b

a)

$a^nb^m\ \ where\ mn\ge0$

b)

$b^ma^n\ \ where\ mn\ge0$

c)

$a^nb^m\ \ where\ mn>0$

d)

$a^nb^m\ \ where\ m\ge n$

21.

let L1 and L2 be context free language and regular language, respectively. Then which of the following statement is True

a)

Compliment of L1 is not regular

b)

Compliment of L2 is not regular

c)

Compliment of L2 is regular

d)

L1-L2 is not a context free

22.

L1: { $0^p1^q0^r,\ where\ p=q\ and\ pqr\ge0$ }

L2: $0^p1^q0^r,\ where\ p=q\ =r,\ and\ pqr\ge0$

a)

L1 is context free

b)

L2 is context free

c)

L2 is context free

d)

L1 is not a context free

23.

L is a language accepted by the turning machine. x is a string accepted by TM is a

a)

Decidable problem

b)

Undecidable problem

c)

X can be accepted by CFG

d)

X can be accepted by RG

24.

A Grammer G is in Gribach Normal formal. A string "x" of length 5 is accepted by the G. How many step required to achieve the string

a)

9

b)

5

c)

10

d)

4

25.

L1= $a^nb^m\ where\ n=m,\ nm>0\$

L2= $a^nb^m\ where\ nm>0\$

L= L1 U L2 is

a)

L is regular grammar

b)

L is regular but not context free

c)

L is context free only

d)

L is only accpeted by turing machine

26.

Which of the problem is Undeciadable

a)

Membership of CFG's

b)

Ambiguity of Problem of CFGs

c)

Membership of TM

d)

Equivalance of finite state machines

27.

Transition function $\delta$ of NFA i.e Q x $\Sigma$ =

a)

$2^Q$

b)

Q

c)

2XQ

d)

$Q^0$

28.

S-->aBCD

BCD--> DE

D-->aD/a

E--> $\epsilon$ /b

The above grammer is

a)

Type 0 but not type 1

b)

Type 1 but not type 2

c)

Type 2 but not type 3

d)

Type 0,1,2,3

29.

In complexity theory, P1 P2 P3 are three algorithms where P1 & P2 are decidable and Un-decidable, respectively. Which of the following is true?

a)

P3 is decidable if P1 is converted into P3

b)

P3 is undecidable if P3 is converted into P2

c)

P3 is decidable if P3 is converted into P1

d)

P3 is decidable if P3 is converted into inverse of P2

30.

L1 is a Recusive and L2 is Recursive enumerable but not recursive language. Which of the following is True?

a)

Homomorphism of L1 is Resursive

b)

complement of L2 is Recursive enumerable

c)

complement of L1 is Recursive

d)

Homomorphism of L2 is not Resursive enumerable

31.

L1 is a Recusive and L2 is Recursive enumerable but not recursive language. Which of the following is False?

a)

L1 is Recursive Enumerable language

b)

Kleen Clousre of L1 is Recursive

c)

Kleen Clousre of L2 is Recursive

d)

Kleen Clousre of L2 is not Recursive enumerable

32.

L1, & L2 are RL and DCFL . Which of the following is True

a)

L1 $\cup$ L2 is not DCFL

b)

L1 $\cap$ L2 is not DCFL

c)

L1 $\cup$ L2 is CFL

d)

none of the above

33.

Which of the follwing is decidable of Halting turning machine

a)

Ambiguity

b)

Subset

c)

Completeness Problem

d)

Membership

34.

Which of the follwing is Equivalent to RE: $L^+$ + $\epsilon$

a)

Kleen closure $\left(\epsilon\right)$

b)

Positive closure (L)

c)

Kleen closure (Kleen closure (L))

d)

Postive closure (L)

35.

Which of the following Statement is True

a)

L is language is accepted by PDA it means it is a Regular Grammar

b)

L is language is accepted by Finite State automata it means it is a Context sensitive Grammar

c)

L is language is accepted by Finite State automata it means it is a Context Free Grammar

d)

L is language is accepted by PDA it means it is a Context Free Grammar

36.

Which of the following problem is undecidable ?

a)

Membership problem for CFG

b)

Ambuguity of Finite state machine

c)

Equivalent of CFL

d)

Totally of DCLF

37.

$0^p1^q0^r,\ where\ p=q\ =r,\ and\ pqr\ge0$ , Which of the following is true

a)

It is accepted by Finite state machine

b)

it is accepted by PDA

c)

It is accpeted NPDA

d)

It is accepted by Turing Machine

38.

if L and compliment of L is CFL, then L is not

a)

Regular

b)

Context Sensitive

c)

Context Free

d)

Recursive language

39.

L1 and L2 is regular language, then

a)

L1 $\cup$ L2 is not Regular

b)

L1 $\cap$ L2 is not Regular

c)

U-L2 is regular, where U is universal

d)

$R1^+$ is not Regular

40.

L1={10,01,110}, L2={ $\epsilon$ + 101} then L1L2 is

a)

{ $\epsilon$ , 10101,101110}

b)

{10101,10101}

c)

{10110, 10101}

d)

{10101, 101110}

41.

Recursive Enumerable are

a)

is a Type 0

b)

subset of CFL

c)

recognized by Turing machine

d)

all of the above

42.

Inorder to simplify a context free grammar, we can skip the following operation:

a)

Removal of null production

b)

Removal of useless symbols

c)

Removal of unit productions

d)

None of the mentioned

43.

In context to the process of removing useless symbols, which of the following is correct?

a)

We remove the Nullable variables

b)

We eliminate the unit productions

c)

We eliminate products which yield no terminals

d)

All of the mentioned

44.

Given grammar G:

S->aS|A|C

A->a

B->aa

C->aCb

Find the set of variables that can produce strings only with the set of terminals.

a)

{C}

b)

{A,B}

c)

{A,B,S}

d)

None of the mentioned

45.

Suppose A->xBz and B->y, then the simplified grammar would be:

a)

a) A->xyz

b)

b) A->xBz|xyz

c)

c) A->xBz|B|y

d)

d) none of the mentioned

46.

The variable which produces an epsilon is called:

a)

a) empty variable

b)

b) nullable

c)

c) terminal

d)

d) all of the mentioned

47.

Which among the following is the format of unit production?

a)

a) A->B

b)

b) A->b

c)

c) B->Aa

d)

d) None of the mentioned

48.

Given grammar:

S->aA

A->a

A->B

B-> A

B->bb

Which of the following is the production of B after simplification by removal of unit productions?

a)

a) A

b)

b) bb

c)

c) aA

d)

d) A| bb

49.

Which of the production rule can be accepted by Chomsky grammar?

a)

a) A->BC

b)

b) A->a

c)

c) S->e

d)

d) All of the mentioned

50.

Let G be a grammar: S->AB|e, A->a, B->b

Is the given grammar in CNF?

a)

a) Yes

b)

b) No

51.

The format: A->aB refers to which of the following?

a)

a) Chomsky Normal Form

b)

b) Greibach Normal Form

c)

c) Backus Naur Form

d)

d) None of the mentioned

52.

The pumping lemma is often used to prove that a language is:

a)

a) Context free

b)

b) Not context free

c)

c) Regular

d)

d) None of the mentioned

53.

Which of the expressions correctly is an requirement of the pumping lemma for the context free languages?

a)

a) uvⁿwxⁿy

b)

b) uvⁿwⁿxⁿy

c)

c) uv²ⁿwx²ⁿy

d)

d) All of the mentioned

54.

The context free languages are closed under:

a)

a) Intersection

b)

b) Complement

c)

c) Kleene

d)

d) None of the mentioned

55.

Which of the following does not obey pumping lemma for context free languages ?

a)

a) Finite languages

b)

b) Context free languages

c)

c) Unrestricted languages

d)

d) None of the mentioned

56.

Which of the following grammars are in Chomsky Normal Form:

a)

a) S->AB|BC|CD, A->0, B->1, C->2, D->3

b)

b) S->AB, S->BCA|0|1|2|3

c)

c) S->ABa, A->aab, B->Ac

d)

d) All of the mentioned

TOC Gate questions SET-2

Total questions: 56

Worksheet time: 56mins

Similar Resources on Wayground