# Finite Automata

50 %
50 %
Information about Finite Automata
Education

Published on October 26, 2008

Author: mukeshnt

Source: slideshare.net

## Description

Finite Automata

Finite Automata Mukesh N. Tekwani Elphinstone College Mumbai, India 2006 Finite Automata Finite Automata

Nondeterministic Finite Automata A nondeterministic finite automata (NFA) is collection of 5 things or 5 tuple: A set of states S. A set of input symbols ∑ (alphabet) A transition function δ that maps state-symbol pairs to sets of states. A state S 0 (sometimes denoted by Q 0 ) called as the start state or initial state . A set of states F called as the accepting states or final states . An accepting state is denoted by a double circle.

Test if a string matches some pattern. Scan for virus signatures. Process natural language. Search for information using Google. Search for markers in human genome. Access information in digital libraries. Search-and-replace in a word processors. Filter text (spam, NetNanny). Validate data-entry fields (dates, email, URL, credit card). Why study regular expression and DFA?

Test if a string matches some pattern.

Scan for virus signatures.

Process natural language.

Search for information using Google.

Search for markers in human genome.

Access information in digital libraries.

Search-and-replace in a word processors.

Filter text (spam, NetNanny).

Validate data-entry fields (dates, email, URL, credit card).

Deterministic Finite Automata Theoreticians have developed a number of theoretical models to describe &quot;computing&quot; Simplest model is known as a DFA Deterministic : Machine will be in a state. Upon receipt of a certain symbol, it will go to a known state Finite : The machines only have a certain number of states Automata : Machine, robot

Theoreticians have developed a number of theoretical models to describe &quot;computing&quot;

Simplest model is known as a DFA

Deterministic : Machine will be in a state. Upon receipt of a certain symbol, it will go to a known state

Finite : The machines only have a certain number of states

Automata : Machine, robot

DFA's DFA's recognize strings. If the input ends and the DFA is in an accept state then the string is &quot;recognized&quot; A &quot;language&quot; can be described as a set of strings A language is called a regular language if some finite automaton recognizes it. There is a precise mathematical definition of exactly what is meant by a finite automaton

DFA's recognize strings.

If the input ends and the DFA is in an accept state then the string is &quot;recognized&quot;

A &quot;language&quot; can be described as a set of strings

A language is called a regular language if some finite automaton recognizes it.

There is a precise mathematical definition of exactly what is meant by a finite automaton

Parts of a DFA 1 0 1 1 0 accept state transition start state The alphabet for this example is {0, 1}. Each state has a transition for every symbol in the alphabet 2

DFA Examples Example. 1 Accept all strings that end in a 1 q 0 q 1 0 1 1 0 Start

DFA Examples Strings with an odd number of ones. Even Odd 0 0 1 1 Start

DFA Examples Strings containing the substring 001 '001' 0 0 1 1 '0' '00' 0 1 0,1

Finite State Machine (DFA) 0 1 2 3 4 start h e 5 6 8 9 7 ACCEPTED State Machine that recognizes the strings “ he”, “hers”, “his”, and “she”

Finite State Machine (DFA) State Machine that recognizes the strings “ he”, “hers”, “his”, and “she” 0 1 2 3 4 start h e 5 6 8 9 7 ACCEPTED r s

Finite State Machine (DFA) 0 1 2 3 4 start h 5 6 8 9 7 ACCEPTED i s State Machine that recognizes the strings “ he”, “hers”, “his”, and “she”

Finite State Machine (DFA) 0 1 2 3 4 start 5 6 8 9 7 ACCEPTED s h e State Machine that recognizes the strings “ he”, “hers”, “his”, and “she”

Finite State Machine (DFA) 0 1 3 2 start 4 A DFA that recognizes the strings “ and”, & “any” a n d ACCEPTED y

Finite State Machine (DFA) 0 1 3 2 start 4 A DFA that recognizes the strings “ and”, & “any” a n ACCEPTED

Nondeterministic Finite Automata 0 start A NFA that recognizes the strings “and”, & “any” n 1 2 3 4 5 6 d n y a a

Examples Design a DFA to recognize strings that start out with k zeros followed by k ones. Design a DFA to recognize strings with an equal number of ones and zeros. Design a DFA to recognize strings with an equal number of strings &quot;01&quot; and &quot;10&quot;. Impossible? 1 yes 2 No

Design a DFA to recognize strings that start out with k zeros followed by k ones.

Design a DFA to recognize strings with an equal number of ones and zeros.

Design a DFA to recognize strings with an equal number of strings &quot;01&quot; and &quot;10&quot;. Impossible?

1 yes

2 No

Actually the third one is regular! DFA to recognize strings with an equal number of strings &quot;01&quot; and &quot;10&quot; 0 0 0 0 0 1 1 1 1 1 1 0 1 0

## Add a comment

 User name: Comment:

## Related presentations

#### Mobile Repairing Course In Noida

September 23, 2017

#### Digital Marketing Training Company in jaipur Seo T...

September 15, 2017

#### Websharan Infotech Web Devlopment company In Jaipu...

September 18, 2017

#### SCHOOL LEVEL SCHOLARSHIP EXAM

September 23, 2017

#### Top CBSE Schools In Gurgaon | Best CBSE School Ind...

September 23, 2017

#### Non Government Organization Muskan

September 23, 2017

## Related pages

### Finite-state machine - Wikipedia, the free encyclopedia

A finite-state machine (FSM) or finite-state automaton (plural: automata), or simply a state machine, is a mathematical model of computation used to design ...

### Deterministic finite automaton - Wikipedia, the free ...

In theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite state ...

### Finite Automata – Official Site -

Genitorturers w/ Finite Automata The Masquerade! Tuesday Oct 13, 2015. 7PM! Event Page Tickets. Two new shows announced for 2015! Posted on: April 1st, 2015

### Endlicher Automat – Wikipedia

Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine ... Zvi Kohavi: Switching and Finite Automata Theory.

### Definition of Deterministic Finite Automata

Definition of Deterministic Finite Automata Subjects to be Learned. Finite automata State transition diagram State transition table Contents Here we are ...

### Finite Automata - The School of Electrical Engineering and ...

Finite Automata Informally, a state machine that comprehensively captures all possible states and transitions that a machine can take while responding to a ...

### Introduction to Finite Automata - Department Of Computer ...

Introduction to Finite Automata In this chapter we are going to study a class of machines called finite automata. Finite automata are computing devices ...

### Finite automata

Finite automata M.V.Lawson DepartmentofMathematics SchoolofMathematicalandComputerSciences Heriot-WattUniversity Riccarton,EdinburghEH144AS Scotland