Theory of Computation Test 5

Result

Theory of Computation Test 5

Score
-
out of -
Rank
-
out of -

TIME Taken - -

SHARING IS CARING

If our Website helped you a little, then kindly spread our voice using Social Networks. Spread our word to your readers, friends, teachers, students & all those close ones who deserve to know what you know now.

Weekly Quiz Competition

Question 1
1 / -0

Recursive languages are closed under which of the following operations?
I. Union
II. Complement
III. Concatenation
IV. Kleene star

A
I, II and III only

B
I, III and IV only

C
II, III and IV only

D
I, II, III, and IV
Solution
.Concept:
Recursive languages are closed under Union, Complement, Concatenation and Kleene star
Explanation
Let L1 and L2 be recursive languages.
- \(L_1 \cup L_2\)
→ Recursively enumerable languages are under union operation, hence \(L_1 \cup L_2\) is recursive
- \( \overline {L_1} \)
→ Recursive languages are closed under complementation operation, hence \(\overline {L_1}\) is recursive.
- \(L_1 .L_2\)
→ Recursively enumerable languages are closed under concatenation operation, hence \(L_1 .L_2\) is recursive.
- \({L_1}^+\)
→ Recursive languages are closed under Kleene star operation, hence \({L_1}^+\) is recursive
Question 2
1 / -0

Consider the following statement:
(i). The class of languages recognized by three stack Turing machines is exactly the class of Turing recognizable languages.
(ii). Multi-tape Turing machines are more powerful then single tape Turing machines.
(iii). Non deterministic Turing machines are more powerful than deterministic Turing machines.
Which of the the above statement/s is/true?

A
(i) only

B
(i) and (ii) only

C
(ii) and (iii) only

D
All are true

Solution

(i). True: Three Stacks is equivalent to two stacks hence the class of languages recognized by three stack Turing machines is exactly the class of Turing recognizable languages.
(ii). False: Multitape Turing machines has same power as single tape Turing machines.
(iii). False: Non deterministic Turing machines solves problem faster as they split in different copies of them self at every pass.
Question 3
1 / -0

Let L₁ be recursively enumerable language but not recursive, L₂ be recurive language and L₃ be context free language and L₄ be regular language.
Which one of the following statements is/are true?
I. L₁∩ L₂ is recursively enumerable language
II. L^*₃. L^*₄ is context free language
III. L₂ ∩ L̅₂ are recursive language

A
Only I

B
Only I and II

C
Only I and III

D
I, II and III

Solution

Statement 1:
L₁: recursively enumerable language
L₂: recursive language
Every recursive language is recursively enumerable language
Also, recursively enumerable language is closed under intersection
Therefore, L₁∩ L₂ is recursively enumerable language
Statement 2:
L₃: context free language
L₄: regular language
Every regular language is context free language
Also, context free language is closed under Kleene closure and concatenation
Therefore, L^*₃. L^*₄ is context free language
Statement 3:
Recursive language is closed under intersection and complementation
Therefore, L₂ ∩ L̅₂ are recursive language
Question 4
1 / -0

Consider the following problems:
(i) Whether a finite automaton halts on all inputs?
(ii) Whether a given Context Free Language is Regular?
(iii) Whether a Turing Machine computes the product of two numbers?
Which one of the following is correct?

A
Only (ii) and (iii) are undecidable problems

B
(i), (ii) and (iii) are undecidable problems

C
Only (i) and (ii) are undecidable problems

D
Only (i) and (iii) are undecidable problems

Solution

Statement i: Decidable
A language is decidable when there is a machine which halts for every string in that language and goes to non-final state for string not in the language. A finite automaton is a special case of a Turing machine which halts on all inputs that are in the language, so it is decidable.
Statement ii: Undecidable
Regular property of context free languages is undecidable. This can be proved by taking regular language as Σ^*. Assume both G and R as part of input problem. For any family of languages, whether it is equal to other language is decidable if both L₁ and L₂ are subset of each other.
Statement iii: Undecidable
Turing machine is for recursive enumerable languages (for type 0 problems). Type 0 problems are undecidable. If we do not know about the Turing machine, it could possible that result for any two numbers will go into infinite loop and never halt. If it happens, then problem is undecidable.
Question 5
1 / -0

Let L₁ and L₂ be recursively enumerable languages over the alphabet Σ such that L₁ ∩ L2 = ϕ and L₁ ∪ L₂ = Σ* Which of the following statements is/are FALSE?
I. L1 and L2 are both recursive
II.The complements of L1 and L2 are both recursively enumerable.

A
Only I

B
Only II

C
Both 1 and II

D
Neither I nor II

Solution

Since L₁ ∩ L₂ = ϕ and L₁ U L₂ =Σ*, we get \(\overline {{L_1}} = {L_2}\ and\ \overline {{L_2}} = {L_1}.\)Thus, the complements of L₁ and L₂ are both recursively enumerable.
Also, L₁ and L̅ ₁ are both recursively enumerable, L₁ is recursive. Similarly, L₂ is also recursive.
Therefore I and II both are correct
Hence none of them are false
Question 6
1 / -0

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.

A
Only I, II and III

B
Only II, III, IV, V

C
II, IV only

D
All are possible

Solution

(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