Q) Applications of Regular Expressions:

1. Lexical Analysis:
One of the major applications of regular expressions is in specifying the component called “lexical
analyzer”. This component scans the source program and recognizes all tokens, those substrings of
consecutive characters that belong together logically. Keywords and identifiers are common examples of
tokens.
2. Finding patterns in text:
Regular expression gives a “picture” of the pattern we want to recognize. By using regular expressions, it
becomes easy to describe the patterns at a high level with little effort and to modify the description quickly
when things go wrong. The regular are the then compiled into DFA or NFA which are then simulated to
produce program that recognizes patterns in text.

Q) Closure Properties of Regular Sets:

Closure properties express the idea that when one ( orseveral) languages are regular, then certain related
languages are also regular.
The following summarizes the principal closure properties for regular languages:
1. The union of two regular languages is regular.
2. The intersection of two regular languages is regular.
3. The complement of two regular languages is regular.
4. The difference of two regular languages is regular.
5. The reversal of regular language is regular.
6. The closure of a regular language is regular.
7. The concatenation of regular languages is regular.
8. A homomorphism of a regular language is regular.
9. The inverse homomorphism of a regular language is regular.

Q) Decision Properties of Regular Language:

1) Testing Emptiness of Regular Languages:
 The emptiness question is whether there is any path from the start state to some accepting state. If so,
the language is non empty, while if accepting states are all separated from the start state, then the
language is empty.
 Deciding whether we can reach an accepting state from the start state is a simple instance of graph
reachability.
2) Testing Membership in a Regular Language:
 Here the question is given a string w and a regular language L, is w in L.
 If L is represented by a DFA, simulate the DFA processing the string input symbols w, beginning in
the start state. If the DFA ends in an accepting state, the answer is yes otherwise the answer is no.
 If L has any other representation besides a DFA we could convert to a DFA and then run the test
above.

By : Prof. Bharti Khemani 1

 3) Testing Equivalence of States:
 To find states that are equivalent, we try to find pairs of states that are distinguishable. Any pair of
states that we do not find distinguishable are equivalent.
 The table filling algorithm is a recursive discovery of distinguishable pairs in a DFA.
4) Testing Equivalence of Regular Languages:
 The table filling algorithm gives us an easy way to test if two regular languages are the same.
Suppose L and M are two languages represented by their respective DFA’s.
 Now test if the start states of the two original DFA’s are equivalent, using the table filling algorithm.
If they are equivalent, then L = M and if not then L ≠ M.

Q) Applications of FA:
1) Lexical Analyzer:
Lexical Analyzer (which performs one of the phases of Compilation i.e. Lexical Analysis) groups the series
of characters into one of these token types (which can be identifier, operator symbol, punctuation symbol,
etc). The set of words belonging to a particular token type is a regular language. Hence each of these token
types can be specified using regular expressions.
Example: consider the token Identifiers Identifier
can be defined by regular expression as
r = (letter). (letter | digit)*
letter = A | B | …|Z | a | b|… | z
digit = 0 |1 |…| 9
So one can specify all the token types using regular expressions. These regular expressions are then
converted into a DFAs.
2) Searching using Regular Expressions in Text Editors:
Many operating systems provide search utilities to perform frequent and complex jobs. The search command
simulates the finite automata corresponding to the regular expressions (i.e the word to be searched).

Q) Recursive Language:
A language L over the alphabet  is called recursive if there is a TM T that accepts every word in L and
rejects every word in L.
i.e. Accept (T) = L
reject (T) = L
loop (T) = 
Example: TM accepting L over Σ = {a, b} that starts with a and rejects all other. So L Language is recursive.
Q) Recursively Enumerable Language:
A language L over the alphabet  is called r.e. if there is a TM T that accepts every word in L and either
rejects or loops for every word in language L.
i.e. Accept(T) = L

By : Prof. Bharti Khemani 2

reject(T) + loop(T) = L’
Example: A TM accepting a language L = { anb na n } and loops or rejects all words not in L. So { anb na
n } is r.e.

Q) Rice’s Theorem:

Q) Pumping Lemma for Regular Sets:

Let L be a regular set. Then there is a constant n, such that if z is in L and |z| >= n, then we may write z=uvw
in such a way that
1) |uv| ≤ n, and
2) |v| >= 1
3) for all i >= 0 uviw is in L.
Theorem Let M = (Q, , , q0, F) be a finite automaton with n states.
Let L be the regular set accepted by M. Let w є L and |w| ≥ m.
If m ≥ n, then there exists x, ,y and z such that w =xyz, y≠ /\ and xyi z є L for each i≥ 0.
Pumping Lemma for CFL’s:

By : Prof. Bharti Khemani 3

Let L be any CFL. Then there is a constant n, depending only on L, such that if z is in L and |z| >= n, then
we may write z=uvwxy such that
1) |vx| >= 1
2) |vwx| ≤ n, and
3) for all i >= 0 uviwxiy is in L.
Proof: Our first step is to find a CNF grammar G for L. Suppose that z is in L is of length atleast n.
Q) Applications of Pumping Lemma:
The pumping lemma can be used to prove a variety of languages not to be context free.

Q) Universal Turing Machine (UTM):

A Universal Turing Machine (UTM) is a Turing Machine (TM) which is all powerful or universal in the
sense that it is capable of doing anything that any other TM can do. In other words, the UTM should have
the capability of imitating any Turing machine ‘T’ given the following information in its tape:
The description of ‘T’ in terms if its operation or program area of the tape (i.e. the transition table). The
initial configuration of the TM i.e. starting state or the current state and the symbol scanned. The processing
data to be fed to ‘T’ (data area of the tape).
This obviously means that the UTM should have an algorithm to interpret correctly the rules of operation
given about the TM ‘T’. The behavior of the UTM is simple, namely, simulating ‘T’ one step at a time as
follows:
A marker to indicate the point at which the description of ‘T’ begins, and it keeps a complete account of
how the tape of ‘T’ looks like at every instant guides it. Also, it remembers the state ‘T’ is in, and the
symbol ‘T’ is reading. Then it simply looks at the description of ‘T’ to carry out what ‘T’ is supposed to do.
In order to exhibit this behavior, the UTM should have a lookup facility and should perform the following
steps:
Step 1: Scan the square on the state area of the tape and read the symbol that ‘T’ reads and initial state of
‘T’.
Step 2: Find the triplet which corresponds to the initial state and the input symbol read in step1. (triplet :
new state, new symbol to be replaced and direction of move).
Step 3: Move the tape to reach the appropriate square in the data area, replace the symbol, move the tape in
the required direction, read the next symbol and finally reach state area and replace the state and scanned
symbols. Go to step 1.
The UTM laid the foundation for:
• Stored program computers and
• Interpretative implementation of programming languages.
Q) Variations of Turing Machine:
1. Turing Machine with Two Way Infinite Tape:
A Turing Machine with a two infinite tape is denoted by
M = ( Q, , , , q0,B, F) as in the original model.
As it name implies, the tape is infinite to the left as well as to the right. We imagine that there is infinity of
blank cells to the left and the right of the current nonblank portion of the tape. L is recognized by a Turing

By : Prof. Bharti Khemani 4

Machine with a twoway infinite tape if and only if it is recognized by a Turing Machine with a oneway
infinite tape.
2. TM with Semi-infinite tapes:
Till now we have allowed the tape head of TM to move either left or right from its initial position., it is only
necessary that the TM’s head be allowed to move within the positions at and to the right of the initial head
position. In TM with Semi-infinite tapes there are no cells to the left of the initial position.
3. Multitape Turing Machine:
A multitape Turing machine consists of a finite control with k tape heads and k tapes; each tape is infinite in
both directions.
On a single move, depending on the state of the finite control and the symbol by each of the tape heads, the
machine can:
 Change State
 Print a new symbol on each of the cells scanned by its tape heads.
 Move each of its tape heads, independently, one cell to the left or right, or keep it stationary.

4. Multihead Turing Machine:

A k-head Turing Machine has fixed number, k, of heads. The heads are numbered 1 through k, and a
move of the TM depends on the state and on the symbol scanned by each head. In one move, the heads
may each move independently left, right or remain stationary.
5. Nondeterministic Turing Machine:
A nondeterministic Turing Machine is a device with a finite control and a single one-way infinite tape.
For a given state and tape symbol scanned by the tape head, the machine has a finite number of choices
for the next move.
Each choice consists of a
• New state
• Tape Symbol to print
• Direction of head motion
6. Multidimensional Turing Machine:
It is a device having a finite control and the tape consists of a k-dimensional array of cells infinite in all 2k
directions for some fixed k. Depending on the state and the symbol scanned, the device
• Changes state
• Prints a new symbol
• Move the tape head in one of 2k directions either positively or negatively along with one of the k
axes.
7. Composite T.M.:
Two or more Turing Machines can be combined to solve a collection of simpler problem, so that the output
of one TM forms the input to the next TM and so on. This is called as Composition.
The idea of composite TM gives rise to the concept of breaking the complicated job into number of jobs
implementing each separately and then combining them together to get answer for the job required to be
done.
8. Iterated T.M.:
In Iterated TM the output it applied to the input repetitively.

Q) Halting Problem:
For a given configuration of a TM two cases can arise:
• the machine starting at this configuration will halt after a finite number of steps.
• the machine starting at this configuration never halts no matter how long it runs.
Given any TM, problem of determining whether it halts ever or not, is called as halting problem.

By : Prof. Bharti Khemani 5

To solve the halting problem, we should have some mechanism to which given any functional matrix, input
data type and initial configuration of the TM for which we want to detect, determines whether the process
will ever halt or not.
Note : In reality, one cannot solve the halting problem. The halting problem is unsolvable. That means there
exists no TM, which can determine whether a given program including itself, will ever halt, or not.
Proof: - Let us prove the halting problem by contradiction. Suppose that there exists a TM ‘A’ which
decides whether or not any computation by a TM ‘T’ will ever halt, given the description ‘dT’ of ‘T’ and the
tape ‘t’ of ‘T’. Then for every input (t, dT) to ‘A’,
if ‘T’ halts for the input ‘t’, ‘A’ reaches an “accept halt”;
if ‘T’ does not halt for the input ‘t’, then ‘A’ reaches an “reject halt”. (fig a)

Q) Consequences of Halting Problem:

1) We cannot decide whether a TM ever prints a given symbol of its alphabet. This is also unsolvable.
2) Two TM’s with the same alphabet cannot be checked for equivalence or inequivalence by an algorithm;
i.e. there is no effective general way to decide whether a given computational process will ever terminate or
whether two given processes are equivalent. This is also another unsolvable problem.
3) Blank –tape theorem: There exists a TM which when started on a Blank tape, can write its own
description. This is of interest in constructing self-reproducing machine.
Q) UnDecidability:
• A problem whose language is recursive is said to be decidable otherwise it is undecidable. If the
problem is undecidable then there is no algorithm which takes the input and find the answer either
YES or NO.
• The problem “whether a TM will halt for the given input word” is an undecidable problem.
Q) UnSolvalibity:
• If there is a TM which, when applied to any problem in the class, always eventually terminates with
the correct (yes/no) answer, we call the problem solvable
• If there is a TM which, when applied to any problem in the class, always eventually terminates with
the correct answer when the answer is yes and may or may not terminate when the correct answer is
no, we call the problem semi-solvable or partially solvable.
• If there is no TM which, when applied to a problem in the class, eventually terminates with the
correct answer yes, we call the problem unsolvable.
Q) Posts Correspondence Problem (PCP):
Post’s Correspondence Problem (PCP) was first introduced by Emil Post in 1946. Later, the problem was
found to have many applications in the theory of formal languages.
The problem over an alphabet  belongs to a class of yes / no problems and is stated as follows :
Consider the two lists x = (x1 . . . . xn), y = (y1 . . . . yn) of nonempty strings over an alphabet  = (0, 1).
The PCP is to determine whether or not there exist i1 . . . .., im, where o  ij  n, such that xi1, . . . . xim =
yi1, . . . . yim
The aim is to arrange tiles in such order that string made by Numerators is same as string made by
Denominators. In simple words, lets assume we have two lists both containing N words, aim is to find out

By : Prof. Bharti Khemani 6

concatenation of these words in some sequence such that both lists yield same result. Let’s try
understanding this by taking two lists A and B A=[aa, bb, abb] and B=[aab, ba, b]
Now for sequence 1, 2, 1, 3 first list will yield aabbaaabb and second list will yield same string aabbaaabb.
So the solution to this PCP becomes 1, 2, 1, 3.
Note :
1) The indices ij’s need not be distinct and m may be greater than n.
2) if there exists a solution to PCP, there exists infinitely many solutions
3) PCP is undecidable.

By : Prof. Bharti Khemani 7