Free Printable CA-II_TOC

1.

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

2.

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

3.

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

4.

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

5.

$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$

6.

RE= (01+11)*

How many states need to design a minimum DFA?

a)

2

b)

3

c)

1

d)

4

7.

Which of the following statement is true ?

a)

Containing aaa

b)

any number of "a" followed by "b"

c)

any number of "b" followed by "a"

d)

Multiple of a where a mod 3 =0

8.

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$

9.

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

10.

L1= S-->aSB/ab

L2= S--> Sab/ab

P:L1 is regular language

Q: L2 is context free language

Which of following statement true?

a)

P true and Q False

b)

Q true and P False

c)

P true and Q True

d)

P False and Q False

11.

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

12.

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

13.

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

14.

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

15.

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

16.

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

a)

$2^Q$

b)

Q

c)

2XQ

d)

$Q^0$

17.

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

18.

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

19.

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

20.

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

21.

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

22.

Which of the follwing is decidable of Halting turning machine

a)

Ambiguity

b)

Subset

c)

Completeness Problem

d)

Membership

23.

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)

24.

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

25.

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

26.

$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

27.

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

a)

Regular

b)

Context Sensitive

c)

Context Free

d)

Recursive language

28.

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

29.

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

a)

{ $\epsilon$ , 10101,101110}

b)

{10101,10101}

c)

{10110, 10101}

d)

{10101, 101110}

30.

Recursive Enumerable are

a)

is a Type 0

b)

subset of CFL

c)

recognized by Turing machine

d)

all of the above

CA-II_TOC_Gate

Total questions: 30

Worksheet time: 3600secs

Similar Resources on Wayground