An Introduction to

Formal Languages and

Automata
Peter Linz
What is Automata?
• A machine or control mechanism designed to follow automatically a predetermined
sequence of operations or respond to encoded instructions.

• Thermostats, automatic pilots of aircraft (device for controlling an aircraft), missile guidance systems,
telephone networks, and controls of certain kinds of automatic elevators are all forms of automata.

• The best known general automaton is the modern electronic computer, the internal states of which are
determined by the data input and which operates to produce a certain output.
Finite automata are a useful model as……

1. Software for designing and checking the behaviour of digital circuits

2. The lexical analyser of a typical compiler, that is, the compiler component
that breaks the input text into logical units

3. Software for scanning large bodies of text, such as collections of Web

pages, to find occurrences of words, phrases or other patterns

4. Software for verifying systems of all types that have a finite number of
distinct states, such as communications protocols for secure exchange
information
Automata theory teaches you the very important
equivalence between….

a language: some -- usually -- infinite set of strings

a grammar: the finite set of rules to generate that language

an automaton: the abstract processing device that can recognize that
language
• Automata theory and formal languages are the base of current

compilers,
regular expressions,
parsers,
web-scrappers,
natural language processing (NLP),
Automata play a major role in theory of computation,
compiler construction, artificial intelligence, parsing and
formal verification.
• Theory of computation deals with how efficiently problems can be solved on
a model of computation - that describes how a set of outputs are computed for a
given a set of inputs….

• A compiler is a computer program that transforms computer code written in one

programming language (the source language) into another programming
language (the target language).

• Parsing, syntax analysis, or syntactic analysis is the process of analysing a string

of symbols, either in natural language, computer languages or data structures,
conforming to the rules of a formal grammar
• Automaton that contains all features of a digital computer . It accepts
input, produces output, and have temporary storages and can make
decisions in transforming the input into output.

• Formal Language is the general characteristics of programming

language which consist of set of symbols and some rules where
symbols can be combined into sentences.

• Finally we formalize the concept of mechanical computation by giving

a precise definition of the term algorithm.
Computation

CPU memory

8
temporary memory

input memory
CPU
output memory

Program memory

9
 3
Example: f ( x ) x

temporary memory

input memory
CPU
output memory
Program memory

compute xx
2
compute x x
 3
f ( x) x

temporary memory
input memory
x 2
CPU
output memory
Program memory
compute xx
2
compute x x 11
 3
temporary memory f ( x) x
z 2 * 2 4
f ( x) z * 2 8
input memory
x 2
CPU
output memory
Program memory
compute xx
2
compute x x 12
 3
temporary memory f ( x) x
z 2 * 2 4
f ( x) z * 2 8
input memory
x 2
CPU
f ( x) 8
Program memory output memory
compute xx
2
compute x x
 Automaton
temporary memory

Automaton

CPU input memory

output memory
Program memory

14
 Different Kinds of Automata
Automata are distinguished by the temporary memory

• Finite Automata: no temporary memory

• Pushdown Automata: stack

• Turing Machines: random access memory

15
 Finite Automaton

temporary memory

input memory
Finite
Automaton
output memory

Example: Vending Machines

(small computing power)
16
 Pushdown Automaton

Example: Compilers for Programming Languages

(medium computing power) 17
 Turing Machine

Random Access
Memory

input memory
Turing
Machine
output memory

Examples: Any Algorithm

(highest computing power) 18
 Power of Automata

Finite Pushdown Turing

Automata Automata Machine

Less power More power

Solve more
computational problems
19
Three Basic Concepts

Languages
Grammar
Automata

Finite non empty sets Ʃ of symbols called alphabets

From individual symbols we construct strings which are finite sequence
of symbols from the alphabet.
If Ʃ = { a,b} then abab, aaabbba are some of the strings on Ʃ
We use lowercase letters a, b, c… for elements of Ʃ
We use u, v , w for string names
Example w = abaaa
Languages:

Empty string is the string with no symbols and denoted by λ

• If w = vu then the substrings v and u are prefix and suffix of w
Example 1: w = abbab
Prefix : { λ, a,ab,abb,abba, abbab} is the prefixes of w
Suffix : {abbab, bbab, bab, ab, b, λ }

Example 2: w = aabcd
Prefix : { λ, a,aa,aab,aabc, aabcd}
Suffix : {aabcd, abcd, bcd, cd,d, λ }
Recursive Definition of Length: (Exam point of view no proofs
required. We solve problems based on proofs.)
• If u and v are strings, then the length of their concatenation is the sum of the individual length.
ie.
• If w is a string, then wn stands for string obtained by repeating w, n times.
w0 = λ.

• Ʃ*  includes λ and Ʃ+  Ʃ* - λ

• Ʃ is finite where Ʃ* and Ʃ+ are always infinite.

• Let L = { a, aa, ab, abb} on Ʃ then

• = Ʃ* - L
• L* = L0 U L1 U L2 U ….. (star closure)
• L0 = {λ}
• L1 = L
• L2 = L . L
• L+ = L1 U L2 U….. (positive closure) Note: in place of Epsilon (ɛ) use Lambda (λ)

• A string in a Language L will be called as sentence of L.

• If L = {λ, ab, abab …..} then find L2
L2 = L.L = {λ, ab, abab …..} {λ, ab, abab …..}
= {λ, ab, abab …..}
=L
Therefore L2 = L

Now, L = {λ, ab, a2b2, a3b3 …..} then find L2

Grammars

(two sets are said to be disjoint sets if they have no element in

common.)
The production x  y implies

ie. w derives z or z is derived from w

If
If the strings contains variables and terminals then they are called as sentential form
Example:
S  aAb | λ productions
A  aAb | λ

S  aAb  aaAbb  aabb in this aaAbb and aAb are in sentential form
a , b are terminals
A - Variables
aabb is a string ie. w
• G = ( {S}, {a,b}, S, P) with P given by
S  aSb | λ

Option 1:
Sλ
S  aSb
The language generated by this grammar is
S a λb
S  ab
L= { anbn | n >= 0}
Option 2:
S  aSb L = { λ, ab, aabb, aaabbb…..}
S  a aSbb
S  aa λbb
S  aabb
• Language Definition:
If G = (V, T, S P) is a grammar then language L generated by grammar G is
L (G) = { w ϵ T * | S  w}
Example 1:
G = ( { S,A}, {a,b}, S, P}
S  Ab
A  aAb
Aλ

S  Ab  aAbb  aaAbbb  aa A bbb  aaa A bbbb  aaa λ bbbb  aaabbbb

So
L = { an bn+1 | n >= 0}
• Let G be a grammar G = ( {S}, {a,b}, S, P)

S  SS S  SS  aSbS  aaSbbS  aabbS  aabb

S  aSb
S  SS  SaSb  S abSa b  abSab  abab
S  bSa
Sλ
So The language generated by this grammar is
L = { w | na (w) = nb (w) }
• Equivalent Grammar
Let G1 and G2 be any 2 grammars. Then if L (G1) = L (G2) then 2 grammars are
equivalent.
Let G1 be…..
S  aSb | λ
S aSb  aaSbb  aa λ bb  aabb
L = { anbn | n >= 0}

Let G2 be…..
S  aAb | λ
A  aAb | λ
S aAb  aaAbb  aa λ bb  aabb
L = { anbn | n >= 0}
So L (G1) = L (G2)
Some Examples
Find the Language generated by this grammar
1. G = ( {S}, {a,b}, S,P)

S  SS | aSb | bSa | λ

Find the Grammar for the Language

2. L = { (01)n | n >=0} or L= { w | w ϵ {01}* }

3. L = { wwr | w ϵ {a,b}*}

4. L = { 0n 12n | n >=0}

5. L = { an bn - 3 | n >=3}
Automata
Input file

Storage

Control unit

output

• Abstract model of digital computer

• Input file is divided into cells each can hold one symbol

• Read the input file from left to write one at a time

• Temporary storage device with unlimited no. of cells each capable of holding one symbol

• Automaton can read and change the content of storage cells

• Control unit will be in some internal state

• The internal state of CU at the next time step is determined by transition function

• Transition function gives the next state in terms of current state, current input symbol, current
information in the storage.

• The term configuration is used to refer to a particular state of CU, input file and temporary
storage.

• The transition of automaton from one configuration to next is called a move.

Transition Graph a, b

q5 Reject state
a, b
b a a b
q0 a q1 b q2 b q3 a q4

initial accepting
state state
transition
Next state
40
Initial Configuration
Input String
a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

41
Reading the Input
a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

42
a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

43
a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

44
a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

45
 Input finished

a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

accept
46
Two types of Automata

1. Deterministic Automata (DFA)

2. Nondeterministic Automata (NFA)

DFA – In this each move is uniquely determined by the current

configuration.
δ (q0 ,a) = q0

δ (q0 ,b) = q1
NFA – It has several possible moves. So we can predict a set of possible
actions.

δ (q0 ,a) = { q0, q1, q2 }

Accepter: An automaton whose output response is limited to sample

“Yes” or “No” is called accepter ie. Either accept the string or rejects it.
Transducer: Automaton capable of producing strings of symbols as
output .
• Some Applications
• An automaton can be represented by a graph in which the vertices give the internal states and
the edges give the transitions. The labels on the edges show what happens (in terms of input and
output) during the transition.

• The above Figure represents a transition from State 1 to State 2, which is taken when the input
symbol is a.

This is an automaton that accepts all legal C identifiers. When the first
symbol is a letter or an underscore, the automaton goes into State 2,
after which the rest of the string is immaterial. State 2 therefore
represents the “yes” state of the accepter. Conversely, if the first
symbol is a digit, the automaton will go into State 3, the “no” state,
and remain there.
Serial Binary Adder:
 A binary addition table summarizes the process

We represent the automaton by a graph now labeling the edges (ai, bj)/di.
Comparison Acceptor and
Transducer
Fig 1.9

Fig 1.6

Transducer

Acceptor