Option 2 : Every subset of recursively enumerable set is recursive

- Power of DFA is equal to NFA so Every NFA can be converted into equivalent DFA as well as Every DFA can be converted into equivalent NFA.
- Power of DTM is equal to NTM so Every NTM can be converted into equivalent DTM as well as Every DTM can be converted into equivalent NTM.
- Regular language is subset of context-free language, so every regular language is a context-free language
- Recursive language is subset of recursive enumerable language so subset of a recursively enumerable set is may or may not be recursive.

Chomsky Hierarchy:

Therefore option 2 is the correct answer.

Option 2 : closed under intersection.

C is false as the set of all recursively enumerable languages (semi-decidable) is a STRICT super set of the set of all recursive languages (decidable).

D is false as the set of all recursively enumerable languages (set of all Turing machines) is an infinite but countable set.

If L and P are two recursively enumerable languages, then they are not closed under

Option 4 : Set difference

\(L−P=L∩P^C\) as recursively enumerable languages are not closed under complementation they are not closed under set difference.

Let L_{1} be recursively enumerable language but not recursive, L_{2} be recurive language and L_{3} be context free language and L_{4} be regular language.

Which one of the following statements is/are true?

I. L_{1 }∩ L_{2} is recursively enumerable language

II. L^{*}_{3 }. L^{*}_{4} is context free language

III. L_{2} ∩ L̅_{2} are recursive language

Option 4 : I, II and III

__Statement 1:__

L_{1}: recursively enumerable language

L_{2}: recursive language

Every recursive language is recursively enumerable language

Also, recursively enumerable language is closed under intersection

Therefore, L_{1 }∩ L_{2} is recursively enumerable language

__Statement 2:__

L_{3}: context free language

L_{4}: regular language

Every regular language is context free language

Also, context free language is closed under Kleene closure and concatenation

Therefore, L^{*}_{3 }. L^{*}_{4} is context free language

__Statement 3:__

Recursive language is closed under intersection and complementation

Therefore, L_{2} ∩ L̅_{2} are recursive language

Let L_{1} be recursive language and L̅_{1 }be its complement. Also, L_{2} be the rsively enumerable language which is not recursive and L̅_{2} be its complement. Let A and B be two languages such that L̅_{2} reduces to A and B reduces to L̅_{1} and the reduction is many to one. Which of the following is/are true?

I. B is recursive language

II. B may or may not be recursive language

III. A can be recursively enumerable language

IV. A is not recursively enumerable language

Option 3 : I and IV

- If L
_{1}is recursive language (REC) then L̅_{1}is also REC and recursive language is decidable. B reduces to L̅_{1}Since L̅_{1}is decidable then B is also decidable and decidable languages are recursive. - L
_{2}is recursively enumerable language (REL) but not REC and hence L̅_{2 }is also not REL. Since L̅_{2}reduces to A then A is also not REL.

Option 2 : Every subset of recursively enumerable set is recursive

- Power of DFA is equal to NFA so Every NFA can be converted into equivalent DFA as well as Every DFA can be converted into equivalent NFA.
- Power of DTM is equal to NTM so Every NTM can be converted into equivalent DTM as well as Every DTM can be converted into equivalent NTM.
- Regular language is subset of context-free language, so every regular language is a context-free language
- Recursive language is subset of recursive enumerable language so subset of a recursively enumerable set is may or may not be recursive.

Chomsky Hierarchy:

Therefore option 2 is the correct answer.

Let L be a regular language and R be a Turing recognizable but not acceptable language. Which of the following is possible?

I) Compliment of R can be Turing recognizable.

II) L ∪ (R)' can be recursive(where ' is complement operation).

III) Set of all strings common in R' and L can be in not RE.

IV) L ∪ R can be recursive.

V) Set of strings common in R' and L can be Recursive.

Option 2 : Only II, III, IV, V

(I). Compliment of R will be in not-re hence it can not be Turing recognizable.

(II). Assume L is Σ*

(III). Again assume L is Σ*

(IV). Again assume L is Σ*

(V). Assume L is an empty language.

**Example:**

If a, b, and c are the input symbol present in languages.

L = (a + b + c)*, R is RE but R' is not RE (RE is note closed under complementation)

__Statement II:__

L = L ∪ R'

L ∪ R^{' }is regular and hence it is REC in this case

__Statement III:__

Also, the common string of L and R' is not RE

__Statement IV:__

L = L ∪ R

L = L ∪ R is regular and hence it is REC in this case

__Statement V:__

if L = ϕ

L = L ∩ R' = ϕ is REC

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is necessarily true?

I L2 – L1 is recursively enumerable.

II L1 – L3 is recursively enumerable

III L2 ∩ L1 is recursively enumerableOption 3 : I and III

- \(L2 - L1 = L2 \cap \;\overline {L1} \)

→ Recursive languages are closed under complementation, hence \(\overline {L1}\) is recursive. Since every recursive language is recursively enumerable. Therefore \(L2 - L1\) is recursively enumerable.

- \(L1 - L3 = L1 \cap \;\overline {L3} = \overline {L3}\)

→ Recursively enumerable languages are not closed under complementation, hence \(\overline {L3}\) may or may not be recursively enumerable language and so \(L1 - L3\) is may or may not be recursively enumerable.

- \(L2 \cap L1\)

→ Recursively enumerable language is closed under intersection. Hence \(L2 \cap L1\) is recursively enumerable.

Which of the following is/are true among the below given statements?

Option :

** Option 1) **TRUE

L = { e(T) | e(T) ϵ L(T) } is Recursive Enumerable but not Recursive because we cannot decide whether the binary encoding of T belongs to language accepted by T or not. Hence the problem is Semi-decidable but not decidable, which means it is Recursive Enumerable but not Recursive.

** Option 2) **FALSE

The given language L = { T | T is a machine which rejects its own coding } is known as “Diagonalization language” and that is NOT Recursive Enumerable because if a machine cannot accept its encoding then no machine can be designed for it.

** Option 3) **TRUE

__Post correspondence problem (PCP) __– To check whether a combination of string in language A is equivalent to a string in language B is known as PCP.

Post correspondence problem (PCP) is Undecidable as the combination cannot be predicted as there exist infinite no. of solution.

** Option 4) **FALSE

“Is the complement of a Recursive Enumerable language is also a Recursive Enumerable” is Undecidable problem because Recursive Enumerable language are not closed under complement operation.

What is the language generated by the below given grammar?

S → aabbcc/aaAbbcc

Abb → bbA

Acc → Bbbcccc

bbB → Bbb

aaB → aaaa/aaaaA

(let n be natural number in options)Option 4 : L = a^{2n}b^{2n} c^{2n }where n ≥ 1

Smallest string that can be derived from the above given grammar is

S → aabbcc

∴ option 1 and option 3 has been eliminated

Second smallest string that can be derived from the given grammar is

S → aa**Abb**cc

S → aabb**Acc**

S → aa**bbB**bbcccc

S → **aaB**bbbbcccc

S → aaaabbbbcccc

Option 2 is eliminated because