Theory of Computation Exam Questions with Answers

Give the DFA accepting the strings over {a, b} such that each string does not start with ab.

Here’s the DFA (Deterministic Finite Automaton) that accepts strings over the alphabet {a, b} such that each string does not start with “ab”:

States:

q0: Initial state
q1: Accepting state
q2: Dead state (to indicate the string starts with “ab”)
Transitions:

From state q0:

On input ‘a’, transition to state q1 (any string starting with ‘a’ is accepted).
On input ‘b’, transition to state q2 (to indicate the string starts with ‘ab’).
From state q1:

On input ‘a’ or ‘b’, remain in state q1 (continue accepting any subsequent characters).
From state q2:

On any input ‘a’ or ‘b’, remain in state q2 (rejecting any further characters).
This DFA can be represented as follows:

In this DFA:

q0 is the initial state.
q1 is the accepting state.
q2 is the dead state indicating the string starts with “ab”, and any further characters will be rejected.

Give the regular expression for the following languages.
a. L= {SS {a, b}* and S starts with aa or b and does not contain substring bb .
b. {0, 1}* and 0 occurs in pairs if any and ends with 1.

a. For the language �={��∣{�,�}∗ and � starts with �� or � and does not contain substring ��}L={SS∣{a,b}∗ and S starts with aa or b and does not contain substring bb}:

(aa | b)[ab]*(a | ε)

b. For the language �={0,1}∗L={0,1}∗ where 00 occurs in pairs (if any) and the string ends with 11:

(00)*1

What is a multi-track Turing Machine? How does it differ with the single-track machine?

A multi-track Turing Machine is a type of Turing Machine (TM) that has multiple tapes, each consisting of multiple tracks. In a traditional single-track Turing Machine, there is only one tape with a single track, which the machine uses to read, write, and move the tape head.

Here are some key differences between a multi-track Turing Machine and a single-track Turing Machine:

Number of tapes/tracks:

Single-track TM: It has only one tape with a single track.
Multi-track TM: It has multiple tapes, each consisting of multiple tracks. Each track can hold its own symbol independently.
Tape head movement:

Single-track TM: The tape head moves left or right along the single track.
Multi-track TM: Each tape has its own tape head, and each tape head can move independently in either direction along its track.
Read/write operations:

Single-track TM: The single tape head reads a symbol from the current cell, writes a symbol to the current cell, and moves left or right.
Multi-track TM: Each tape head can read a symbol from its current track, write a symbol to its current track, and move independently of other tape heads.
Complexity:

Single-track TM: Generally simpler to analyze and understand due to its single-track nature.
Multi-track TM: Can potentially handle more complex tasks due to the ability to manipulate multiple tapes simultaneously.
Multi-track Turing Machines are more powerful in terms of computational ability compared to single-track Turing Machines because they can perform multiple operations concurrently on different tracks. However, this increased power comes with increased complexity in analyzing and understanding their behavior and computational properties.

What is an algorithm? Explain on the basis of Church Hypothesis.

An algorithm is a well-defined, step-by-step procedure or set of rules that outlines how to solve a particular problem or perform a specific task. It is a finite sequence of instructions that can be executed by a computing agent, such as a computer, to achieve a desired outcome. Algorithms are fundamental to computer science and are used in various fields to automate processes, make decisions, and solve problems efficiently.

The Church-Turing Thesis, also known as the Church Hypothesis, is a foundational concept in computer science and mathematics that states that any effectively computable function can be computed by a Turing Machine. This hypothesis was independently proposed by Alonzo Church and Alan Turing in the 1930s, providing a theoretical framework for understanding the limits of computation.

Alonzo Church formulated his thesis using the concept of lambda calculus, a formal system for expressing computation based on functions and substitutions. Lambda calculus provides a mathematical model of computation that is equivalent in power to Turing Machines. Church proposed that any computable function can be expressed as a lambda expression and computed using lambda calculus.

Alan Turing, on the other hand, introduced the concept of Turing Machines, which are abstract mathematical models of computation. A Turing Machine consists of an infinite tape divided into cells, a read/write head that moves along the tape, and a finite set of states and transition rules. Turing Machines can perform various operations, including reading and writing symbols on the tape, moving the tape head left or right, and changing states based on predefined rules.

The Church-Turing Thesis asserts that any function that is effectively computable can be computed by a Turing Machine or expressed in lambda calculus. In other words, if an algorithm exists to solve a particular problem, it can be implemented using either Turing Machines or lambda calculus. This thesis provides a theoretical foundation for understanding the capabilities and limitations of computation, serving as a guiding principle in the development of algorithms and computing systems.

Show that a language L is accepted by some DFA if and only if L is accepted by s.

To prove that a language �L is accepted by some DFA (Deterministic Finite Automaton) if and only if �L is accepted by some regular expression �s, we need to show two implications:

1. If a language �L is accepted by some DFA, then it is accepted by some regular expression �s.
2. If a language �L is accepted by some regular expression �s, then it is accepted by some DFA.

Let’s prove each implication separately:

1. If a language �L is accepted by some DFA, then it is accepted by some regular expression �s:

Let �M be a DFA that accepts the language �L. We can construct a regular expression �s that represents the language �L as follows:

1. Let �Q be the set of states of �M.
2. For each state �q in �Q, define a regular expression ��Rq​ that represents the language of strings that lead from the start state to state �q, considering all possible paths.
3. Let �F be the set of final states of �M. For each final state �f in �F, add the regular expression ��Rf​ to the final regular expression �s.
4. The regular expression �s is the union of all regular expressions ��Rf​ for �f in �F.

This regular expression �s represents the language accepted by �M, which is equivalent to the language �L.

2. If a language �L is accepted by some regular expression �s, then it is accepted by some DFA:

Let �s be a regular expression that represents the language �L. We can construct a DFA �M that accepts the language �L as follows:

1. Construct a non-deterministic finite automaton (NFA) �N from the regular expression �s using Thompson’s construction algorithm.
2. Convert the NFA �N to a DFA �M using the subset construction algorithm.

The DFA �M accepts the same language as the regular expression �s, which is equivalent to the language �L.

Therefore, we have shown both implications:

• If a language �L is accepted by some DFA, then it is accepted by some regular expression �s.
• If a language �L is accepted by some regular expression �s, then it is accepted by some DFA.

Hence, we conclude that a language �L is accepted by some DFA if and only if �L is accepted by some regular expression �s.