[go: up one dir, main page]
Scribd
Upload
120 views21 pages

Theory of Automata: Ntroduction

The document provides an introduction to automata theory. It defines key terms like automata, alphabet, strings, languages, grammars, and the Chomsky hierarchy. It discusses the central concepts of automata theory, including finite automata and deterministic finite automata (DFAs). As an example, it shows how to build a DFA that recognizes binary strings containing the substring "01".

Uploaded by

Umair Bashir
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
120 views21 pages

Theory of Automata: Ntroduction

The document provides an introduction to automata theory. It defines key terms like automata, alphabet, strings, languages, grammars, and the Chomsky hierarchy. It discusses the central concepts of automata theory, including finite automata and deterministic finite automata (DFAs). As an example, it shows how to build a DFA that recognizes binary strings containing the substring "01".

Uploaded by

Umair Bashir
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
You are on page 1/ 21

Theory of Automata

INTRODUCTION

Engr. Umair Bashir


Department ofComputer Engineering
engineerumairbashir@gmail.com
What is AutomataTheory?
What is AutomataTheory?

• The term "Automata" is derived from the Greek word "αὐτόματα" which
means "self-acting“.
• A moving mechanical device made in imitation of a human being.
What is AutomataTheory?

• Study of abstract computing devices, or “machines”


• Automaton = an abstract computing device
A “device” need not even be a physical hardware!
• A fundamental question in computer science:
• Find out what different models of machines can do and cannot do
• The theory of computation
• Computability vs. Complexity
Alan Turing (1912-1954)

• Father of Modern ComputerScience


• English mathematician
• Studied abstract machines called Turing machines even before computers
existed
• Heard of the Turing test?
Languages & Grammars

• Languages: “A language is a collection of


sentences of finite length all constructed
from a finite alphabet of symbols”
• Grammars: “A grammar can be regarded as
a device that enumerates the sentences of a
language” - nothing more, nothing less

• N. Chomsky, Information and Control,Vol 2,


1959
The Chomsky Hierachy

• A containment hierarchy of classes of formal languages

Recursively-
enumerable

Context
sensitive

Context free

Regular DFA
The Central Concepts of Automata Theory?
Alphabet
An alphabet is a finite, non-empty set of symbols
• We use the symbol ∑ (sigma) to denote an alphabet
• Examples:
• Binary: ∑ = {0,1}
• All lower case letters: ∑ = {a,b,c,..z}
• Alphanumeric: ∑ = {a-z, A-Z, 0-9}
• DNA molecule letters: ∑ = {a,c,g,t}
• …
Strings
A string or word is a finite sequence of symbols chosen from ∑
• Empty string is  (or “epsilon”)
• Length of a string w, denoted by “|w|”, is equal to the number of (non- ) characters in the
string
• E.g., x = 010100 |x| = 6
• x = 01  0  1  00 |x| = ?

• xy = concatentation of two strings x and y


Powers of an alphabet

Let ∑ be an alphabet.

• ∑k = the set of all strings of length k

• ∑* = ∑0 U ∑1 U ∑2 U …

• ∑+ = ∑1 U ∑2 U ∑3 U …
Languages
L is a said to be a language over alphabet ∑, only if L  ∑*
 this is because ∑* is the set of all strings (of all possible length including 0) over the given
alphabet ∑
Examples:
1. Let L be the language of all strings consisting of n 0’s followed by
n 1’s: L = {, 01, 0011, 000111,…}
2. Let L be the language of all strings of with equal number of 0’s
and 1’s: L = {, 01, 10, 0011, 1100, 0101, 1010, 1001,…}

Definition: Ø denotes the Empty language


• Let L = {}; Is L=Ø?
The Membership Problem

Given a string w ∑*and a language L over ∑, decide whether or not w L.

Example:
Let w = 100011
Q) Is w  the language of strings with equal number of 0s and 1s?
Finite Automata

• Finite automata are finite collections of states with transition rules that take
you from one state to another.
• Finite automata have finite state space with finite alphabets(symbols).
• For a finite automata we have: MDFA = {S,∑ ,δ ,S0 ,F}
• Original application was sequential switching circuits, where the “state” was
the settings of internal bits.
Action

State
Representing Finite Automata

• Initial State
• Dead state
• Final state
• Arcs indicate state transitions.
• Labels on arcs tell what causes the transition
Deterministic Finite Automata

• A Deterministic Finite Automaton (DFA) consists of:


• Q ==> a finite set of states
• ∑ ==> a finite set of input symbols (alphabet)
• q0 ==> a start state
• F ==> set of accepting states
• δ ==> a transition function, which is a mapping between Q x ∑ ==> Q
• A DFA is defined by the 5-tuple:
• {Q, ∑ , q0,F, δ }
Example: DFA

• Build a DFA for the following language:


• L = {w | w is a binary string that contains 01 as a substring}
• Steps for building a DFA to recognize L:
• ∑ = {0,1}
• Decide on the states:Q
• Designate start state and final state(s)
• δ: Decide on the transitions:
• “Final” states == same as “accepting states”
• Other states == same as “non-accepting states”
DFA for strings containing 01

• Q = {q0,q1,q2}
• ∑ = {0,1}
• start state = q0
• F = {q2}
• Transition table

You might also like