Finite Automata

50 %
50 %
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 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

 User name: Comment:

May 23, 2018

May 23, 2018

May 23, 2018

May 23, 2018

May 23, 2018

May 23, 2018

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