CS3452 – THEORY OF COMPUTATION
UNIT I AUTOMATA AND REGULAR EXPRESSIONS
PART A (2 MARKS) (QUESTIONS WITH ANSWER)
1. Define hypothesis. R
The formal proof can be using deductive proof and inductive proof. The deductive
proof consists of sequence of statements given with logical reasoning in order to prove the
first or initial statement. The initial statement is called hypothesis.
2. What is structural induction?
To prove a property of the elements of a recursively defined set, we use structural induction.
Basis Step: Show that the result holds for all elements specified in the basis step of
the recursive definition.
Inductive Step: Assume that the property holds for the elements currently in the
recursively defined set.
Show that it is true for each of the rules used to construct new elements in the recursive step
of the definition.
3. Define deductive proof.
Deductive proof consists of a sequence of statements whose truth leads from some
initial statement, called the hypothesis to a conclusion statement. Each step in the proof must
follow some accepted logical principle, from either the given facts or some previous in the
deductive proof or a combinations of these.
4. Define Set, Infinite and Finite Set. R
Set is Collection of various objects. These objects are called the elements of the set.
Eg : A = { a, e, i, o, u }
Infinite Set is a collection of all elements which are infinite in number.
Eg: A = {a | a is always even number}
Finite Set is a collection of finite number of elements. Eg : A = { a, e, i, o, u }
5. Define Non-Deterministic Finite Automata.
The finite automata are called NFA when there exists many paths for a specific
input from current state to next state.
A finite automata is a collection of 5 tuples (Q, Σ. δ, q0, F )
where Q is a finite set of states, which is non-empty.
Σ is a input alphabet, indicates input set.
δ is a transition function or a function defined for going to next state.
q0 is an initial state (q0 in Q)
F is a set of final states
PART B (13 MARKS) (QUESTIONS WITH ANSWER)
1. Construct a DFA equivalent to the NFA. M= ({p,q,r},{0,1}, δ, p,{q,s}) Where δ is defined
in the following table.
KEY ANSWER
To construct a DFA (Deterministic Finite Automaton) equivalent to the given NFA
(Nondeterministic Finite Automaton), we'll use the subset construction method. Here's the
given NFA:
M = ({p, q, r}, {0, 1}, δ, p, {q, s})
The transition table (δ) for the NFA is not provided in the question. Please provide the
transition table or the transition function (δ) for each state and input symbol in the NFA, and
I'll be happy to help you construct the equivalent DFA.
2. Construct NFA with ε which accept all strings over alphabet £ =(a,b,c) which string
contains multiple of a's followed by multiple b's followed by multiple of c's.
KEY ANSWER
To construct an NFA with ε transitions that accepts all strings over the alphabet Σ = {a, b, c}
which contain multiples of 'a's followed by multiples of 'b's followed by multiples of 'c's, we
can follow these steps:
1. Start with three states: S1, S2, and S3. S1 will represent the state for multiple 'a's, S2 for
multiple 'b's, and S3 for multiple 'c's.
2. Set S1 as the initial state and S3 as the accepting state.
3. Add ε transitions from S1 to S2, and from S2 to S3. These transitions allow skipping from
one segment of multiple characters to another.
4. Add transitions for each character of the alphabet:
- From S1, add transitions for 'a' to itself (S1) and ε to S2.
- From S2, add transitions for 'b' to itself (S2) and ε to S3.
- From S3, add transitions for 'c' to itself (S3).
5. Finally, add a transition from S3 to a new trap state (St) for any character 'a', 'b', or ε. This
state will be used to reject strings that contain additional characters after the multiple 'c's
segment.
Here's the formal representation of the NFA with ε transitions:
N = ({S1, S2, S3, St}, {a, b, c}, δ, S1, {S3})
The transition function (δ) is defined as follows:
δ(S1, a) = {S1}
δ(S1, ε) = {S2}
δ(S2, b) = {S2}
δ(S2, ε) = {S3}
δ(S3, c) = {S3}
δ(S3, a) = {St}
δ(S3, b) = {St}
δ(St, a) = {St}
δ(St, b) = {St}
δ(St, c) = {St}
Note: The trap state (St) is a non-accepting state that is used to reject strings that contain
additional characters after the multiple 'c's segment.
3. Construct a DFA equivalent to the NFA given below:
KEY ANSWER
To construct a DFA (Deterministic Finite Automaton) equivalent to a given NFA
(Nondeterministic Finite Automaton), we can use the subset construction method. However,
since you haven't provided the details or transition table of the NFA, I cannot proceed
without that information.
Please provide the complete description or transition table of the NFA, including the set of
states, alphabet, transition function, initial state, and set of accepting states. With that
information, I'll be able to assist you in constructing the equivalent DFA.
4. Convert the following ε-NFA to DFA
KEY ANSWER
To convert an ε-NFA (Nondeterministic Finite Automaton) to a DFA (Deterministic Finite
Automaton), we can use the subset construction method. The given ε-NFA should consist of
states, alphabet, transition function, initial state, and set of accepting states. Please provide
the complete details or transition table of the ε-NFA, and I'll assist you in constructing the
equivalent DFA.
