Select the operation from the options in which DCFL is closed but CFL is not closed.
Union
Intersection
Complement
Concatenation
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Select the operation from the options in which CFL is closed but DCFL is not closed.
Union
Intersection
Complement
Concatenation
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Consider the following problems.

PA = { M is a dfa that accepts input string w }

PB = { M is an nfa that rejects input string w }

Select the correct option.

Both PA and PB are decidable.
PA is decidable while PB is undecidable.
PA is undecidable while PB is decidable.
Both PA and PB are undecidable.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Consider the following statements.

S1: Given two regular expressions R1 and R2, whether they are equivalent is an undecidable problem.

S2: Given two NFAs, whether they accept same language is an undecidable problem.

Select the correct option.

Both S1 and S2 are true.
S1 is true while S2 is false.
S1 is false while S2 is true.
Both S1 and S2 are false.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Select the operation from the option in which DCFL is closed.
Set difference
Kleene star
Kleene plus
Reversal
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
If L is recursively enumerable. Then

L and 𝐿̅ must be recursive.
L must be recursive but 𝐿̅ need not be.
Either L is recursive or 𝐿̅ is not recursively enumerable.
None of above
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66

Both S1 and S2 are true.
S1 is true while S2 is false.
S1 is false while S2 is true.
Both S1 and S2 are false.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider the below mentioned problems.

S1: M is a TM and L(M) is regular.

S2: M is a TM and L(M) is finite.

Select the correct option.

Both S1 and S2 are decidable.
S1 is decidable but S2 is undecidable.
S1 is undecidable but S2 is decidable.
Both S1 and S2 are undecidable.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider the below mentioned problems?

S1: M is a LBA that accepts string w.

S2: M is a LBA where L(M) =Φ

Select the correct option.

Both S1 and S2 are decidable.
S1 is decidable but S2 is undecidable.
S1 is undecidable but S2 is decidable.

Both S1 and S2 are undecidable.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Which of the following statement is false?
CFL’s are closed over the operation of string reversal.
Every subset of regular is regular.
If a language L is accepted by a non-deterministic Turing machine M1, then L must be accepted by some deterministic Turing machine M2.
If a language L is accepted by a multi-tape Turing machine, then L must be accepted by a single-tape Turing machine.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider the following languages, here M is encoding of some Turing machine.

L1={<M> | M is a TM and M has 21 states}

L2={<M> | M is a TM and M doesnot have a halt state (final state) }

Select the correct option.

Both S1 and S2 are decidable.
S1 is decidable but S2 is undecidable.
S1 is undecidable but S2 is decidable.
Both S1 and S2 are undecidable.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider the following languages.

L1: {<M,w> | M is a TM which accepts string w}.

L2: {<M,w> | M is a TM which rejects string w}

Select the correct option.

Both S1 and S2 are decidable.
S1 is decidable but S2 is undecidable.
S1 is undecidable but S2 is decidable.
Both S1 and S2 are undecidable.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider the following languages.

L1: {<M> | M is a TM such that L(M)=φ}.

L2: {<M> | M is a TM such that L(M)≠φ }

Select the correct option.

Both S1 and S2 are decidable.
S1 is decidable but S2 is undecidable.
S1 is undecidable but S2 is decidable.
Both S1 and S2 are undecidable.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider the following languages.

L1: {<M> | M is a Finite automata such that L(M) is finite}.

L2: {<M> | M is a TM such that L(M) is infinite }

Select the correct option.

Both S1 and S2 are decidable.
S1 is decidable but S2 is undecidable.
S1 is undecidable but S2 is decidable.
Both S1 and S2 are undecidable.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider the following languages.

L1: {<M> | M is a TM and L(M) is countable}.

L2: {<M> | M is a TM and L(M) is uncountable }

Select the correct option.

Both S1 and S2 are decidable.
S1 is decidable but S2 is undecidable.
S1 is undecidable but S2 is decidable.
Both S1 and S2 are undecidable.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66