Paper Id- 411411

B. TECH
(SEM IV) THEORY EXAMINATION 2023-24
THEORY OF AUTOMATA AND FORMAL LANGUAGES

Subject Code: BCS402

Section - A
Ans 1(a)
A deterministic finite automaton is set of five tuples represented as,
M = (Q, Σ, δ, q0, F)
Where,
Q: A non-empty finite set of states in the finite control(qo, q1, q2, …).
Σ: A non-empty finite set of input symbols.
δ: It is a transition function that takes two arguments, a state, and an input symbol, it returns a
single state.
qo: It is starting state, one of the states in Q.
F: It is a non-empty set of final states/ accepting states from the set belonging to Q.
DFA NFA
DFA stands for Deterministic Finite NFA stands for Nondeterministic
Automata. Finite Automata.
For each symbolic representation of the No need to specify how does the NFA
alphabet, there is only one state transition react according to some symbol.
in DFA.
DFA cannot use Empty String transition. NFA can use Empty String transition.
In DFA, the next possible state is In NFA, each pair of state and input
distinctly set. symbol can have many possible next
states.
DFA is more difficult to construct. NFA is easier to construct.

Answer 1 (b)
Answer 1 (c)

Answer 1 (d)

Answer 1 (e)

Ans 1(f)
A Two-Stack Pushdown Automaton (PDA) is a theoretical computational model that extends
the traditional Pushdown Automaton by using two stacks instead of one. This model is more
powerful than a single-stack PDA and can recognize a broader class of languages,
specifically all languages that are context-sensitive.
Definition:
A Two-Stack PDA is a 7-tuple (Q,Σ,Γ,δ,q0,Z0,F)(Q, \Sigma, \Gamma, \delta, q_0, Z_0,
F)(Q,Σ,Γ,δ,q0,Z0,F)
Q: A finite set of states.
Σ: A finite set of input symbols (input alphabet).
Γ: A finite set of stack symbols (stack alphabet).
δ: A transition function Q×(Σ∪{ϵ})×Γ×Γ→Q×Γ∗×Γ∗Q that defines state transitions based on
the current state, input symbol, and top symbols of both stacks.
q0∈Q: The start state.
Z0∈Γ: The initial stack symbol.
F⊆Q: A set of accept states.

Example: L = {an bn cn | n>=1}

The language L = {an bn cn | n>=1} consists of strings with equal numbers of 'a's, 'b's, and 'c's
in that order. This language is not context-free because it requires counting and matching three
different segments of symbols. A single-stack PDA cannot handle this requirement because it
can only keep track of two segments at most (using push and pop operations). However, a two-
stack PDA can manage this by using both stacks to enforce the counting and matching of three
segments.

Ans 1(g)

Multi-tape Turing Machines have multiple tapes where each tape is accessed with a separate
head. Each head can move independently of the other heads. Initially the input is on tape 1
and others are blank. At first, the first tape is occupied by the input and the other tapes are
kept blank. Next, the machine reads consecutive symbols under its heads and the TM prints a
symbol on each tape and moves its heads.

Note − Every Multi-tape Turing machine has an equivalent single-tape Turing machine.
 Section – B
Answer 2(a)
Answer 2 (b)
Answer 2 (c)
Answer 2(d)

Answer 2 (e)
 Section – C
Answer 3 (a)
Answer 3 (b)

Answer 4 (a)
The Pumping Lemma for regular languages is a property that all regular languages satisfy. It is often
used to prove that certain languages are not regular by showing that they do not satisfy this property.

Statement of the Pumping Lemma:

If L is a regular language, then there exists a positive integer p (called the pumping length)
such that any string s in L with length ∣s∣≥p can be divided into three parts, s=xyz, satisfying
the following conditions:

1. ∣xy∣≤p.
2. ∣y∣≥1 (i.e., y is not an empty string).
3. For all i≥0, the string x yi z is also in L.

Proof by Contradiction
Step 1 - Assume L is Regular:
Assume, for the sake of contradiction, that L is regular. By the Pumping Lemma, there exists
a pumping length p such that any string s in L with ∣s∣≥p can be split into three parts s=xyz
satisfying the pumping lemma conditions.

Step 2. Choose a Specific String s in L:

Let’s choose a specific string s in L where s= aq and q is a prime number such that q ≥ p.

Step 3. Apply the Pumping Lemma:

According to the lemma, s=aq can be decomposed into xyz where:

 ∣xy∣≤p
 ∣y∣≥1
 For all i≥0, xyiz ∈L

Since ∣xy∣≤p, and ∣y∣≥1, the length of y is at most p and y is not empty. Therefore, y= aq
where k≥1. The string s= aq can be split as follows:

 x= am
 y= an
 z= ak
 Thus, m + n + k = q, where n≥1 and m + n ≤ p.

Step 4. Test the Pumping Condition with i = 2:

Consider xy2z:
 xy2z= am (an)^2 ak = am + 2n + k
Let p=q, where p is the pumping length. So, xy2z = aq + n.
Step 5 - Show the Contradiction:
Since q is a prime number, q + n must be checked if it is also a prime number:
 If n≥1, q + n > q.
 The number q + n (where n≥1) is generally not guaranteed to be a prime number. For
instance, if q=5 and n=1, q + n=6, which is not prime.

Thus, the language L = {ap | Where p is a prime} is not regular.

Answer 4 (b)
A set is closed under an operation if applying that operation to any members of the set always
yields a member of the set.
Closure Properties of Regular Language:
(i) Union: If L1 and L2 are regular languages, then their union L1 U L2 is also a regular
language.
Proof: Let M1 and M2 be two finite Automata that accept the L1 and L2 regular
languages, respectively. If we wish to demonstrate that the union of L1 and L2 is
likewise a regular language, we may do the following:
a. Make a new starting point.
b. Make ε -transitions from the new state to each of M1 and M2's original states.

(ii) Concatenation
Concatenation of two regular languages is also regular.

Proof: Let M1 and M2 be two finite automata, and L1 and L2 be the languages that
M1 and M2 accept, respectively. We aim to demonstrate that L1L2 = L, i.e., their
concatenation yields regular language. Let M be a finite automaton composed of
M1 and M2.

(iii) Intersection
 The set of regular languages is closed under intersection.
 Each state in the product is pair of states from the original machines.
Formally, if L1 is accepted by DFA M1 with 5- tuple (Q1 ,Σ, q1 , T1 , δ1 ) and
L2 is accepted by DFA M2 with 5-tuple (Q2 ,Σ, q2 , T2 , δ2 ). Then L1 ∩ L2
is accepted by the DFA (Q1 × Q2 ,Σ,(q1 , q2 ), T1 × T2 , δ) where δ((r, s), x) =
(δ1 (r, x), δ2 (s, x)).
(iv) Complement
The set of regular languages is closed under complementation.
Proof − Let us take a regular expression –
RE = (aa)*
So, L = {ε, aa, aaaa, aaaaaa, .......} (Strings of even length including Null)
Complement of L is all the strings that is not in L.
So, L’ = {a, aaa, aaaaa, .....} (Strings of odd length excluding Null)
RE (L’) = a(aa)* which is a regular expression itself.
(v) Difference
The difference of two regular set is regular.
Proof − Let us take two regular expressions − RE = a (a*) and RE = (aa)*
So, L1 = {a, aa, aaa, aaaa, ....} (Strings of all possible lengths excluding Null)
L2 = { ε, aa, aaaa, aaaaaa,.......} (Strings of even length including Null)
L1 – L2 = {a, aaa, aaaaa, aaaaaaa, ....} (Strings of all odd lengths excluding Null)
RE (L1 – L2 ) = a (aa)* which is a regular expression.
Answer 5 (a)
Answer 5 (b)
Answer 6 (a)
Answer 6 (b)
Answer 7 (a)
Answer 7 (b)

Universal Turing Machine

A Universal Turing Machine is a theoretical model of computation proposed by mathematician

Alan Turing in 1936. It is a type of Turing Machine that can simulate the behaviour of any
other Turing Machine.
In simple terms, a Universal Turing Machine is like a "computer" that can compute any
algorithmic computation that can be carried out by any other Turing Machine. It achieves this
by reading the description of another Turing Machine from its input tape. This description
specifies the states and transitions of the other Turing Machine and enables the Universal
Turing Machine to simulate the behaviour of the other machine on its own tape.
Once the Universal Turing Machine has read the description of the other Turing Machine, it
creates a new tape to simulate the behaviour of the other machine. The Universal Turing
Machine then reads the input tape once again, and uses the simulated Turing Machine to
compute the desired output. The output is then written onto the output tape, and the Universal
Turing Machine stops.
The Universal Turing Machine is considered one of the fundamental concepts in computer
science and is the theoretical foundation of modern computing. It demonstrates the power of a
single, general-purpose computing device and is a testament to the concept of algorithmic
computation.
The schematic diagram of the Universal Turing Machine is as follows −

Post Correspondence Problem

"The Post's correspondence problem consists of two lists of string that are of equal length
over the input. The two lists are A = w1, w2, w3, .... , wn and B = x1, x2, x3, .... xn then there
exists a non empty set of integers i1, i2, i3, .... , in such that,
w1, w2, w3, .... wn = x1, x2, x3, .... xn"
To solve the post correspondence problem we try all the combinations of i1, i2, i3, .... , in to
find the w1 = x1 then we say that PCP has a solution.
Example 1:
Consider the correspondence system as given below
A = (b, bab3, ba) and B = (b3, ba, a). The input set is ∑ = {0, 1}. Find the solution.
Solution:
A solution is 2, 1, 1, 3. That means w2w1w1w3 = x2x1x1x3

Recursive & Recursive Enumerable Language

Recursive Enumerable (RE) or Type -0 Language

RE languages or type-0 languages are generated by type-0 grammars. An RE language can be
accepted or recognized by Turing machine which means it will enter into final state for the
strings of language and may or may not enter into rejecting state for the strings which are not
part of the language. It means TM can loop forever for the strings which are not a part of the
language. RE languages are also called as Turing recognizable languages.
Recursive Language (REC)
A recursive language (subset of RE) can be decided by Turing machine which means it will
enter into final state for the strings of language and rejecting state for the strings which are
not part of the language. e.g.; L= {anbncn|n>=1} is recursive because we can construct a
turing machine which will move to final state if the string is of the form anbncn else move to
non-final state. So the TM will always halt in this case. REC languages are also called as
Turing decidable languages. The relationship between RE and REC languages can be shown
in Figure 1.