Scribd
Upload
7 views13 pages

Introduction to Finite Automata

The document introduces finite automata, defining it as a 5-tuple consisting of states, input alphabet, transition function, initial state, and final states. It discusses undecidability, recursive languages, and recursively enumerable languages, highlighting the characteristics of each. Additionally, it provides examples of the Post Correspondence Problem and outlines exercises related to correspondence systems.

Uploaded by

ratnakar babu M
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
7 views13 pages

Introduction to Finite Automata

The document introduces finite automata, defining it as a 5-tuple consisting of states, input alphabet, transition function, initial state, and final states. It discusses undecidability, recursive languages, and recursively enumerable languages, highlighting the characteristics of each. Additionally, it provides examples of the Post Correspondence Problem and outlines exercises related to correspondence systems.

Uploaded by

ratnakar babu M
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

INTRODUCTION

TO
FINITE AUTOMATA

M RATNAKAR BABU
[Link]. CSE
Prerequisite
• Basic Set theory
Definition

• A finite automata is a collection of 5-tuple(Q,,,q0,F) Where ,


Q is finite set of states, which is non empty.
 is input alphabet, indicates input set.
 is transition function or mapping function. We can determine
the next state using this function.
q0 is an initial state and is in Q.
F is a set of final states.
Undecidability
• A problem is undecidable if there is no Turing machine which will
always halt in finite amount of time to give answer as ‘yes’ or ‘no’.
• An undecidable problem has no algorithm to determine the answer
for a given input.
Recursive Language:
A language ‘L’ is said to be recursive if there exists a Turing
Machine which will accept all the strings in ‘L’ and reject all the
strings not in ‘L’.

The Turing machine will halt every time and give an answer(accept
or reject)for each and every string input.
Undecidability
Recursively Enumerable Language:
A language ‘L’ is said to be recursively enumerable language if
there exists a Turing Machine which will accept all the strings in ‘L’.

But may or may not halt for all input strings which are not in ‘L’.

Undecidable Language:
• A language is undecidable if it is not decidable.
• An undecidable language may sometimes be partially decidable
but not decidable.
• If a language is not even partially decidable, then there exists no
Turing machine for that language.
Undecidability

Recursive Language Turing Machine will always Halt.


Recursively Enumerable Language Turing Machine will Halt
sometimes & May not halt for
sometime
Decidable Language Recursive Language
Partially Decidable Language Recursively Enumerable Language
UNDECIDABLE NO Turing Machine for that
Language.
Example:1
• The post correspondence problem is an undecidable decision
problem that was introduced by Emil Post in 1946.
• For Example consider some set of Dominos which are given as
follows:
Dominos:

B A CA ABC

CA AB A C

We need to find a sequence of dominos such that the Top and Bottom
Strings are the same.
Example:1

ABCAAABC
A B CA A ABC

AB CA A AB C ABCAAABC

• Hence we found the solution for the given PCP


Example:2

A B
10
1 10 101
101
011
2 011 11
11
101
3 101 011
011

Now we need to start with the domino which is having first symbol of
top and bottom are same.
Exercise 1: Consider the correspondence system as
given below- A=(1,0,010,11) and B=(10,10,01,1) The
input set is ={0,1}. Find the Solution.

Exercise 1: Obtain the solution for the


following correspondence system.
A={ba,ab,a,baa,b} and
B={bab,baa,ba,a,aba}.
Summary
• From this session we have seen what is undecidability.

• What is Post Correspondence Problem.

• Example for Post Correspondence Problem.


Next Class
• In the next session we are going to learn about P and NP
completeness.
END For NOW
Continue in next class

You might also like