GTU 3160704 Theory of Computation (TOC) Summer 2023 Question Paper & PDF

Let f be a function from the set 𝐴 = {1,2,3,4} to 𝐵 = {𝑝, 𝑞, 𝑟, 𝑠} such that, 𝑓 = {(1, 𝑝)(2, 𝑝)(3, 𝑞)(4, 𝑠)}. Is 𝑓⁻¹ a function?

Discuss “Distinguishability” of one string from another and explain how it affects the number of states in an FA. Considering the example of 𝐿 = {𝑎, 𝑏}∗{𝑎𝑏𝑎}, how do the distinguishable strings in L relate to the number of states in its FA?

What are similarities and differences between Moore machines and Mealy machines?

𝐿1 = {𝑥 | 𝑎𝑙𝑙 𝑥 𝑠𝑡𝑎𝑟𝑡 𝑤𝑖𝑡ℎ 𝑎𝑏𝑎 } 𝐿2 = {𝑥 | 𝑎𝑙𝑙 𝑥 𝑒𝑛𝑑𝑠 𝑖𝑛 𝑏𝑏} Write the regular expression for both the languages and construct FAs 𝑀1 and 𝑀2 such that 𝑀1 accepts 𝐿1 and 𝑀2 accepts 𝐿2. Derive 𝐿1 ∩ 𝐿2.

For the given Turing Machine in Table-2, trace the transition for the strings 1011 and 10101 and identify the language recognized by this TM. TM is defined as TM = (Q, Σ, Γ, q0, δ ) where {q0,q1,q2,q3,q4,q5,q6} ∈ Q, Σ = {0,1}, {0,1,X,Y,B} ∈ Γ, q0 ∈ Q, B ∈ Γ , B ∉ Σ, {q6} is the accepting state.

Draw only the transition table of Turing Machine to accept the language 𝐿 = {0𝑛1𝑛: 𝑤ℎ𝑒𝑟𝑒 𝑛 ≥ 1}

Define: Bounded Minimalization and show that, if P is a primitive recursive (𝑛 +