Scribd
Upload
15 views10 pages

Understanding Automata Theory Basics

Automata theory deals with mathematical models of computation that are used in areas like text processing, compilers, and hardware design. The finite automata is a common model that has finite states and transitions between states based on inputs. Context free grammars are another model used in programming languages and AI. Proofs in automata theory include deductive, reductive, contradictory, and inductive proofs.

Uploaded by

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

Understanding Automata Theory Basics

Automata theory deals with mathematical models of computation that are used in areas like text processing, compilers, and hardware design. The finite automata is a common model that has finite states and transitions between states based on inputs. Context free grammars are another model used in programming languages and AI. Proofs in automata theory include deductive, reductive, contradictory, and inductive proofs.

Uploaded by

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

Automata

Automata Theory
Automata theory deals with the definitions and properties of
mathemetical models of computation. These models plays a roll in
several applied areas of computer science.

There are two types of mathemetical models-


1. The finite automata is a mathemetical model which is used in
text processing, compilers and hardware design.
2. Second model- context free grammar is used in programming
languages and artificial intelligence.
Finite Automata
The finite automata is a mathemetical model which is used in text
processing, compilers and hardware design.
Most important kinds-
1. Software for designing and checking the behavior of digital
circuits.
2. The lexical analyzer of a typical compiler.
3. Software for scanning large bodies of text.
4. Software for verifying systems having finite number of distinct
states.
Finite Automata
Example 1.1: Push
Start off on

Push
Properties:
1. Finite states.
2. Every state has atleast one input.
3. Transition from one state to another requires an input.
Example 1.2
Structural Representation
1. Grammar: A grammar consists of collection of rules called
productions. Each rule appears as a line in the grammar,
comprising a symbol and a string separated by an arrow. The
symbol is called a variable. The string consists of variables and
other symbols.
A A+1
B A
B #
Structural Representation
2. Regular Expression: Regular expressions are built up with
the help of regular operations. For example-

( 0U1)0*
Where, ( 0U1) means ({0}U{1}).The value of this part is
the language {0,1} and the part 0* means {0}*. The value of this
part is the language consisting of all strings consisting any number
of 0s.
Automata & Complexity
Essential issues for the study of computation:
1. What can a computer do at all?- decidability.
2. What can a computer do efficiently?- intractability.
Proof
A proof is a convincing logical argument that describes a
statement as true.

Types of proof –
1. Deductive Proofs:- ( Theorem 1.3, 1.4),
2. Reductive Proofs:- (Theorem 1.5),
3. Contradictive Proofs:- ( i.e. √2 is rational),
4. Inductive Proofs:- ( Mathemetical Inductions)
Inductive Proof
Inductive proof is an advanced method that is used to show that
all elements of an infinite set have a specified property.

To prove a statement by inductive proof, we have to do two


things-
1. Basis step,
2. Inductive step

** Example-1.19
Some Definitions
1. Alphabet: An alphabet is a finite, nonempty set of symbols.
The members of an alphabet are the symbols of the alphabet. An
alphabet is denoted by ∑.
2. String: A string is a finite sequence of symbols chosen from
some alphabet. It is usually written next to one another and not
separated by commas. For example- if ∑={0,1}, then 01001 is a
string over ∑.
3. Empty String: An empty string is a string with zero occurrences
of symbols or a string of zero length.
4. Language: A language is a set of strings.

You might also like