Lecture 01 - Language Theory and Finite Automata

• Automata
• Symbols
• Alphabet
• Strings
• Language
• Finite Automata
1/21/2024
 Theory of Computation

 Problem → Algorithm → Implement.

 But before writing an algorithm we need see either the problem is

solvable/ computable or not.

 Can we make the mathematical model for that?

 The mathematical model can be Finite automata. Pushdown

automata, or Turing machine.

 This is known as theory of computation.

 Theory of computation is the branch that deals with how efficiently

problems can be solved on a model of computation using an
algorithm.

 The field is divided into three major branches.

 Automata theory and language
 Computational theory
 Computation complexity theory (efficiency).
1/21/2024 2
 Why we study theory of computation

 Behind every implementation there is a theory.

 Theory basically explains the

 Concept
 Principals of that particular theory

 Language Theory  Theory of Computation

 Computation  Task processing by CPU, Calculator etc.

 Theory of Computation  To provide a mathematical model for

computation.

1/21/2024 3
 Language Theory

 Pillars of Theory of Computations.

 LAG

L: Language A: Automata A: Grammar

 Symbol
 Alphabet
 String
 Language

1/21/2024 4
 What we study in this course?
 To know about the laws of computations
 the laws of computation tell us what is (im)possible for computers.
Just like the laws of physics tell us what is (im)possible for nature to do

 In this course we learn what type of the problems

 Can/cannot be computed/solved by computing devices

 In this course we study mathematical models that will describe with

varying degrees of accuracy, parts of computers, types of
computers

 Limitations of those models by input (language)

 Every time we introduce new machine; we will learn its language
 Find a machine for new language

 We will look at different kinds of machines and ask:

 What kinds of problems can this kind of machine solve?
 What things are impossible for this kind of machine?
 Is machine A more powerful than machine B?

1/21/2024 5
 Automata Theory
We will study • We will not study

 Finite Automata • Cellular automata

 Text Processing, Compilers, Hardware • Biology

Design • Buchi automata

 Context Free Grammars • Model checking
 Programming Languages, Artificial • Verification
Intelligence • Concurrency
 Turing Machines
 Theoretical model of Computers,
Essence of Any modern computer.
Precursor for modern computers

1/21/2024 6
 What is an Automata
 Useful model for many important systems, both hardware or
software

 These systems can be viewed as being at all times in one of a

finite number of “states”
 The purpose of a state is to remember the relevant portion of the
system history

 Since there are only a finite number of states, automaton must be

designed carefully.

 The advantage of having a finite number of states is that we can

implement it as a hardware or a software

1/21/2024 7
 Example

• States
 On/off switch • Transitions
• Inputs
• Start state
• Final (accepting) state
push

on off

push

 Modeling recognition of the word “then”

Start state Transition Intermediate Final state

state
1/21/2024 8
 Automata Theory
 Automata theory is the study of abstract machines and problems
which they are able to solve

 A typical abstract machine consists of a definition in terms of

input, output, and the set of allowable operations used to turn
the former into the latter.

 Automata theory is a step in abstracting your attention away

from any particular kind of computer or particular programming
language

1/21/2024 9
 Automata Theory
 In English, we have letter, words and sentences (relationship)
 Not all collection of letters form a valid word, not all collections of
words form a valid sentence
 Same in Computer Languages
 Certain character strings are recognized (do, if, While)
 Certain strings of words are recognizable commands
 Certain set of commands become a program
 Its important to adopt a structure, where the decision whether
certain smaller units constitute a larger unit is based on explicit rules
and not guesswork.
 Its hard to state all the rules for the language ENGLISH
 But in programming languages we can insist on precise rules,
computers cannot understand informal speech

1/21/2024 10
 Formal Languages
 A language in which all rules for language are explicitly stated.

 A formal language is a set of words—that is, strings of symbols

drawn from a common alphabet (a finite set of symbols, letters, or
tokens from which the words of the language may be formed).

 A formal language is often defined by means of a formal

grammar (also called its formation rules).

 Words that belong to a formal language are sometimes called

well-formed words or well-formed formulas.

 The field of formal language theory studies the purely syntactical

aspects of such languages—that is, their internal structural
patterns.

1/21/2024 11
 Formal Languages
 In computer science, formal languages are often used as the basis for
defining programming languages and other systems in which the words
of the language are associated with particular meanings or semantics.
 Software for parsing formal languages may be generated by means of a
compiler, often separated into a lexical analyzer and parser generator.

 In computational complexity theory, decision problems are typically

defined as formal languages, and complexity classes are defined as the
sets of the formal languages that can be parsed by machines with
limited computational power.

 In logic and in the foundations of mathematics, formal languages are

used to represent the syntax of formal theories. Logical systems can be
seen as a formal language with additional constructs, like proof calculi,
which define a consequence relation.

 Formal languages are studied to define things (problems) precisely

 Formal statements have one and only one meanings unlike informal
languages
1/21/2024 12
 Introduction - Basics
 Symbols : Basic building blocks for language
 Symbols  { a, b, 0, 1, or anything like, ψ, Ю, ж, , ……}
we can form

 Alphabet  also called “Sigma” “Σ”

 Alphabet is nothing, just a collection of symbols, i.e., { a, b}
called it set.
we can form

 Set can be anything like {0,1}, {0,1,…9}. There are 2 types of set
 Finite Set: a set having upper bound (ending value), i.e., {0,1, ….
9}, or {a, b, c,….z}
 Infinite Set: a set having no upper bound (no ending value, i.e.,
{0,1,2,….}
 String  { a, b, aa, bb, abb, ….}
 String is nothing, just a sequence of Symbols define over Alphabet
 a  string with length 1.
 aa  string with length 2 etc.

1/21/2024 13
 Introduction - Basics
 String  { a, b, aa, bb, abb, ….}
we can form

 Word  for natural language

 Token  for computer language

 Example:
 Keywords/reserve words, identifiers etc

1/21/2024 14
Introduction - Basics

How many strings are possible for Σ  {a, b} of length 2.

4 Strings are possible

___ ___
a a
a b
b a
b b

1/21/2024 15
 Introduction - Basics
How many strings are possible for Σ  {a, b} of length n.
___ ___ ___ ___ …… __
aa bb ab ba …… n
2 x 2 x 2 x 2 …… n
2n
>
-
length (n)

>
- number of characters (a , b)

We can extends this concepts to any alphabets, as we have only 2

alphabets, that’s why we got 2 n, if there were 3 alphabet then we will take 3 n

 In general, if Σ  |Σ | Then for number of strings of length “n”, we

get |Σ | n
 Where |Σ | represents number of Alphabet and should be positive.
|-2| = 2

1/21/2024 16
Introduction - Language

What is English Language?

An English language in term of Language theory

is nothing, but a collections of words and each
words have specific meanings for human.

1/21/2024 17
 Introduction - Language
 In term of Language Theory: A language is nothing, but a collections of
Strings.
 Example: Σ  {a, b}

 L1 = Set of all strings of length 2  {aa, ab, ba, bb}

 A set of finite strings and we called it Finite Language

 2 n = 2 2= 4

 L2 = Set of all strings of length 3  {aaa, aab, aba, abb, baa, bab, bba, bbb}

 Again, it’s finite language

 2 n= 2 3= 8

 L3 = Set of all strings starting with “a”  {a, aa, ab, aab, aba, ….}

 Because set is infinite and hence L3 is infinite language

 2n

 Length of the string is not given

1/21/2024 18
 Introduction - Language
 Power of Sigma Σ: If Σ  {a, b}

 Σ0  set of all strings of length “0”  {Л} where Л “Lambda”

 Σ1  set of all strings of length “1”  {a, b}

 Σ2  Σ1 Σ1  set of all strings of length “2”  {aa, ab, ba, bb}

 Σ3  Σ1 Σ1 Σ1  set of all strings of length “3”

 | Σ3| |23|  8 strings
:
:

 | Σ|n  “n” length of strings  2n number of strings for 2 alphabet

Σ  {a, b}

1/21/2024 19
 Introduction - Language
 Sigma Σ: If Σ  {a, b}

 Kleene Closure of a language (Star closure)

 Let L be a language over some alphabet Σ then Kleene closure of L is
denoted by L* defined as follows.

 L* = {Set of all Strings over Σ }

 L* = L0 U L1 U L2 U……..

 Σ*  Σ0 U Σ1 U Σ2 ……  {Л} U {a,b} U {aa, ab, ba, bb} U ……

 Σ*  Set of all strings possible over Σ  {a, b} of all length. i.e., include
every string that’s possible over Σ  {a, b}.

 It may be finite / infinite, but it is infinite.

1/21/2024 20
 Introduction - Language
 Positive Closure:
 Let L be a language over some alphabet Σ then positive closure of L is
denoted by L+ defined as follows
 L+ = {Set of all Strings over Σ }

 L+ = L1 U L2 U……..

 Σ+  Σ U Σ*  Σ1 U Σ2 ……  {a,b} U {aa, ab, ba, bb} U ……

 Or Σ+ = Σ*-Σ0

 Example:
 S={0}

 S*={Л, 0, 00, 000, 0000, …..}

 S+={0, 00, 000, 0000, …..}

1/21/2024 21
 Example

 Example, Let’s consider the Languages L1, L2, L3 example.

Σ*  L1 L2 L3 such that L1 ≤ Σ*, L2 ≤ Σ*, L3 ≤ Σ*

How many strings are possible over Σ  {a, b}

How many languages are possible over Σ  {a, b}

For both the answer is Infinite

1/21/2024 22
 Introduction - Language
Why we need to study about “String” or “Language”?

There are many applications. I will explain with

example. Let’s take C-Language example

 Σ  {A…Z, a…z, 0…9, +, - ….} (finite set of symbols)

 All the string for C-Language are build over the above mention Σ
set.
void main(){
 Now Programing example, int a,b;
:
 C-Program Language  set of all “valid” :
}
Programs
Valid  means correct, for invalid you will get error while compiling
1/21/2024 23
Introduction - Language
How many Programs are valid in “C” ?

Let {P1, P2, P3, ……… Pn} ( In-finite set of programs )

So we can called a program is valid, if it belong to the
set above.

How could I find out that the given string is in the

language set or not?

How could you find out that the program is valid or

invalid, it have errors or there’s no error?

Simplest Solution:
1. Save all possible programs on the computer
2. Match the new program within the list one/one
3. If Match == Yes Then given program is valid
4. Else Invalid program
1/21/2024 24
 Introduction - Language
 Solution 2: To define a language over set Σ with a finite set of
strings and then just verify that a given string from any given
program is out of the language or not.

 Example: Σ  {a,b} and L1  { aa, ab, ba, bb}, so the given string
Saaa (to check it is a part of the language or not)

 Simply compare with each string of the language.

 But if L2  {a, ab, aba, ……} then the given string Sababa

 As the Language is infinite, then the given string verification may

be infinite.

1/21/2024 25
 Introduction - Language

Language ( L )

Yes (accept)
String (given) Finite
String
No (Reject)

• The given Language (L) have finite string, where any given
string are match with the finite string of the language.
• if match=Yes then accepted else rejected

1/21/2024 26
 Introduction - Language

Language ( L )

Yes (accept)
String (given) Finite
Automata
No (Reject)

• Finite String replaced by Finite Automata.

What is Finite Automata (FA)?

I will explain it first through examples and then will define.
1/21/2024 27
 Automata

 The plural of the automaton is automata, and automata refer to

“Any object that works automatically”.

 There are two types of languages

1. Formal Languages (also known as Syntactic languages)

2. Informal Languages (also known as Semantic languages)

 Language can also be Finite or infinite

1/21/2024 28
 Introduction – Finite Automata
 Example:

 L1 = Set of all strings start with “a” = { a, aa, aaa, …….}

a
a
A B

 All circles represents states

 The double circle is called “Final State”

 The first circle is called “Initial State”

1/21/2024 29
 Introduction – Finite Automata
 Example:

 L1 = Set of all strings start with “a” = { a, aa, aaa, …….}

a
a
A B

 Given string
a a
 aa A B B

 aaa a a a
A B B B

aaaa…… ?
A String should be valid from the list,
if it leads from initial to final state.
1/21/2024 30
 Introduction – Finite Automata
Case - 02 Case - 03
a, b a, b
a a
A B A B

b
Given String { aa, aab, aba…} a, b
C
a a b
A B B B
babaaa…… ?

babaaa…… ?

We start from the start and end-up

with state “C”, which is not the end-
states. Hence the string is not
approved by the FA.
1/21/2024 31
 Homework
 Design FA for the following languages.

1. Language over {a,b} with all even length words

2. Language over {a,b} with all odd length words

3. Language over {a,b} with words having length 2 or more

4. Language over {a,b} with word length multiple of 3.

5. Language over {a,b} with the number of a’s in each word exactly
2.

6. Language over {a,b} with all the words starting and ending with
the same letters. E.g., if it begins with ‘a’ must end with ‘a’ etc.

7. Language over {a,b} with all the words starting and ending with
opposite letters. E.g., if it starts with the letter ‘a’ must end with
letter ‘b’ and vice versa.
1/21/2024 32
End of Lesson – 01
Thanks to Dr. Irfan

Any questions?

1/21/2024 33