Theory of Computation (DA-1)

NAME: SHIVAM SARASWAT

Reg No: 18BIT0061

1. Write a program in any programming language to simulate

finite automata to validate an identifier.

CODE:
(PYTHON CODE)

NO_OF_CHARS = 256

def getNextState(pat, M, state, x):

'''
calculate the next state
'''

# If the character c is same as next character

# in pattern, then simply increment state

if state < M and x == ord(pat[state]):

return state+1

i=0
# ns stores the result which is next state

# ns finally contains the longest prefix

# which is also suffix in "pat[0..state-1]c"

# Start from the largest possible value and

# stop when you find a prefix which is also suffix
for ns in range(state,0,-1):
if ord(pat[ns-1]) == x:
while(i<ns-1):
if pat[i] != pat[state-ns+1+i]:
break
i+=1
if i == ns-1:
 return ns
return 0

def computeTF(pat, M):

'''
This function builds the TF table which
represents Finite Automata for a given pattern
'''
global NO_OF_CHARS

TF = [[0 for i in range(NO_OF_CHARS)]\

for _ in range(M+1)]

for state in range(M+1):

for x in range(NO_OF_CHARS):
z = getNextState(pat, M, state, x)
TF[state][x] = z

return TF

def search(pat, txt):

'''
Prints all occurrences of pat in txt
'''
global NO_OF_CHARS
M = len(pat)
N = len(txt)
TF = computeTF(pat, M)

# Process txt over FA.

state=0
for i in range(N):
state = TF[state][ord(txt[i])]
if state == M:
print("Pattern found at index: {}".\
format(i-M+1))

def main():
txt = "AABAACAADAABAAABAA"
pat = "AABA"
search(pat, txt)

if __name__ == '__main__':
main()
 2. Explain with examples the real time applications of Finite
Automata, Regular Expressions, and Context free
grammars.

Applications of Finite Automata:

 The optimization of traffic light controllers in a city is a systematic

representation of handling the instructions of traffic rules. Its
process depends on a set of instruction works in a loop with
switching among instruction to control traffic.

 Vending machine is an automated machine that dispenses

numerous items such as cold drinks, snacks, beverages, alcohol
etc. to sales automatically, after a buyer inserts currency or credit
into the machine. Vending machine is works on finite state
automate to control the functions process.

 In electronic appliances, Mealy and Moore machines are used to

test circuits.

 Finite Automata are used in designing of lexical analysis of

compilers and for spell checking in text editors.

Applications of Regular Expressions:

 In websites where users are required to enter their details in

various fields, we can validate the field using various regular
expression i.e data validation.

 Regular expressions are used in internet search engines, search

and replace dialogs of word processors and text editors, in text
processing utilities such as sed and AWK and in lexical analysis.

 It can be used in text processing and sting processing.

Applications of Context free grammer:

 CFG are used in implementing various stack applications.

 CFGs are used in designing the parsing phase of compilers.

  CFGs are used to define the high-level structure of a programming
language.

3. Design a DFA for the following languages using JFLAP tool:

i. L = {abnam : n ≥ 2,m ≥ 3}

M = {Q, q0, F, δ, Σ}
Q = {q0, q1, q2, q3, q4, q5, q6, q7}
q0 = {q0}
Σ = {a,b}
F = {q6}
δ: Q * Σ  Q

ii. L = {bnam: n, m ≥1}

 M= {Q, q0, F, δ, Σ}
Q= {q0, q1, q3, q2}
q0= {q0}
Σ = {a,b}
F={q2}
δ: Q * Σ  Q

4. Construct an NFA that recognizes the regular expression

(aa+bb)(a+b)*

Soln:

M = {Q, q0, F, δ, Σ}
Q = {q0, q1, q3, q2}
q0 = {q0}
Σ = {a, b}
F = {q2}
δ: Q * Σ  2Q
5. State whether L={anbn | n > 0} is non regular.
Soln:

This can be proved by using pumping lemma.

For any regular language L, there exists an integer n, such that for all x
∈ L with |x| ≥ n,

There exists u,v,w ∈ Σ∗, such that x=uvw and

(1) |uv|≤n
(2) |v|≥1
(3) for all i≥0: uviw∈L

Assume pumping length to be 3

For given problem,
L= {anbn}
L= aaabbb

Case 1:
u = aa ; v = ab ; w = bb

If i = 1
uv1w = aaabbb
aaabbb ∈ L

If i = 2
uv2w = aaababbb
aaababbb ∈ L

Case 2:
u = a ; v = aa ; w =bbb
If i = 2
uv2w = aaaaabbb

aaaaabbb does not belongs to L

Therefore, It is proved that L is non-regular language.

6. How to convert a Regular Expression to left-linear grammar
(0+1)*00(0+1)*

Soln:

7. Define regular expression and regular set. Find an equivalent

regular expression to the following DFA-

Soln:

Any set that represents the value of the Regular Expression is called a
Regular Set.
A regular expression is an algebraic formula whose value is a pattern
consisting of a set of strings, called the language of the expression.

Equivalent regular expression:

8. Construct the minimum state automaton equivalent to the

transition diagram:
Sol:

Make a state table for given diagram and use equivalence partitioning to
reduce the diagram into minimum DFA.

Minimized DFA:
9. Every non deterministic finite automaton is a deterministic
finite automaton. If yes, justify your answer with suitable
example.

Soln:

NO, Every NFA is not DFA. Because a finite automata is said to be non-
deterministic if for a particular input symbol, the machine can move
to any combination of the states in the machine.
In other words, the exact state to which the machine moves cannot be
determined. While DFA has definite combination of states in the
machine for a particular input symbol.

Therefore, DFA is a subset of NFA and vice versa is not true. Hence
every NFA can never be DFA.

Eg:
It is a NFA but not a DFA because for input symbol “b”, there is no
resultant state.

10.

Soln:

 We define intial status of each lever to be a 0, then if lever change

direction they go in state 1.
 Each state will be represented as sequence of 3 bits of format lets
say X1X2X3.
 Intial state will be 000. If we drop a marble down B, then the state
becomes to 011 and the marble exits at C.
 Since we have only 3 levers that take only two input i.e 1 and 0 ,
we will have 8 possible states for levers ranging from 000 to 111.
 To identify the states by we need to an “a” for acceptance or “r” for
rejection.
  This will give a total of 16 possible states.
 We need to start from intial state and draw new states as per
inputs from A or B.

Clear Tabular representation of DFA for the Toy:

11. Convert the following context free grammar G into Greibach

Normal Form
S→ AB | 0
A→ BC | 1
B→ CD | 2
C→ AD | 0
D→ 1

Soln:
12.
Solution:

13. Explain the Phases of Compiler with suitable example.

Soln:

Lexical Analysis:
Lexical Analysis is the first phase when compiler scans the source code.
This process can be left to right, character by character, and group these
characters into tokens. The source program is grouped in meaningful
sequences by identifying the tokens. It makes the entry of the
corresponding tickets into the symbol table and passes that token to
next phase.

Example:

x = y * 20

Tokens

X identifier

= Assignment operator

Y identifier

* Multiplication operator

20 Number

Syntax Analysis
Syntax analysis is the second phase of compilation process. The main
aim of this phase is to make sure that the source code was written by
the programmer is correct or not. It is based on the rules based on the
specific programming language by constructing the parse tree with the
help of tokens. It also determines the structure of source language and
grammar or syntax of the language.

Example:

(a+b)*c , the expression is verified using parse tree

Semantic Analysis
Semantic analysis is the third phase of compilation process. It uses the
syntax tree of the previous phase along with the symbol table to verify
that the given source code is semantically consistent. It also checks
whether the code is conveying an appropriate meaning. Semantic
Analyzer will check for incompatible operands, a function called with
improper arguments, an undeclared variable, etc.

Example:

float a = 10.5;

float b = a*10;

In the above code, the semantic analyzer will typecast the integer 10 to
float 10.0 before multiplication

Intermediate Code Generation

In this phase, Compiler generates intermediate code for the target
machine. The Intermediate code is between the high-level and machine
level language. This intermediate code needs to be generated in such a
manner that makes it easy to translate it into the target machine code.

Example:

total = count + rate * 5

Intermediate code with the help of address code method is:

t1 = int_to_float(5)

t2 = rate * t1

t3 = count + t2

total = t3

Code Optimization
This phase removes unnecessary code line and arranges the sequence
of statements to speed up the execution of the program without wasting
resources. The main goal of this phase is to improve on the intermediate
code to generate a code that runs faster and occupies less space.

Example:

Consider the following code

a = int_to_float(10)

b=c*a

d=e+b

f=d

will be converted to

b =c * 10.0

f = e+b

Code Generation
Code generation is the last and final phase of a compiler. It gets inputs
from code optimization phases and produces the page code or object
code as a result. The objective of this phase is to allocate storage and
generate relocatable machine code. It also allocates memory locations
for the variable.

Example:

a = b + 60.0

Would be possibly translated to registers.

MOVF a, R1

MULF #60.0, R2

ADDF R1, R2

----------------------------------------------------

Explanation of all phases using example: Sum = Old sum + Rate*50

14. Explain Linear, Hierarchical, and Semantic Analysis with
suitable example.
Soln:
Linear (Lexical) analysis: In a compiler, linear analysis is called lexical
analysis or scanning. In this case, the stream of characters which make
the source program is read from left to right and generates the tokens
which are sequences of characters having a collective meaning.

Example: In lexical analysis, the characters in the assignment statement

position = initial + rate * 60

would be grouped into the following token:

 The identifier position

 The assignment symbol =

 The identifier initial

 The plus sign

 The identifier rate

 The multiplication sign

 The number 60

The blanks separating the characters of these tokens would normally be

eliminated during lexical analysis.

Hierarchical analysis: Hierarchical analysis is called parsing or syntax

analysis. In this case the tokens of the source program are grouped
hierarchically into grammatical parses that are used by the compiler to
synthesize output.

Example:
position: = initial + rate * 60

In the expression, the phrase rate*60 is a logical unit because the usual
conventions of arithmetic expressions tell us that multiplication is
performed before addition.

Semantic analysis: The semantic analysis phase checks the source

program for semantic errors and gathers type information for the
subsequent code – generation phase. It uses the hierarchical structure
determined by the syntax analysis phase to identify the operators and
operands of expressions and statements. An important component of
semantic analysis is type checking.

Example:

When a binary arithmetic operator is applied to integer and real number.

In this case, the compiler may need to be converting the integer to a
real.