Problem Design an automaton that accepts all strings over {0,1} that have an even length Solution What do you need to remember? Whether you have seen an
| Previous PDF | Next PDF |
[PDF] Deterministic Finite Automata
Problem Design an automaton that accepts all strings over {0,1} that have an even length Solution What do you need to remember? Whether you have seen an
[PDF] Chapter Two: Finite Automata
the finite automaton must reach its decision using the same 2 3 Deterministic Finite Automata The two shortest strings (solutions) in the language are
[PDF] Midterm I (Solutions) CS164, Spring 2002
c) Draw a deterministic finite automaton (DFA) for the language of all strings over the alphabet {0,1} that do not contain the substring 110 Solution: (state D is a
[PDF] Deterministic Finite Automata
Deterministic Finite Automata Definition: A deterministic finite automaton (DFA) consists of 1 a finite set of states (often denoted Q) 2 a finite set Σ of symbols
[PDF] Finite Automata
Finite automata (next two weeks) are an abstraction of computers with finite resource constraints ○ Provide upper bounds for the computing machines Solutions will be available at the practice This is the “deterministic” part of DFA
[PDF] QUESTION BANK SOLUTION Unit 1 Introduction to Finite Automata
Deterministic finite automaton (DFA)—also known as deterministic finite state Obtain a DFA to accept strings of a's and b's starting with the string ab
[PDF] Deterministic Finite Automata A d
A deterministic finite automaton (DFA) over an alphabet A is a finite digraph ( where Solution: (b): Start a, b a, b Solutions: (a): Start a, b (c): Start b a, b a a b
[PDF] Learning of Construction of Finite Automata from Examples - DTIC
with deterministic finite automata, that is, there is at most one 1-arrow and one 0- arrow from each The machines corresponding to these solutions are s follows
[PDF] DD2372 Automata and Languages – Problems from previous exams
Give a DFA for the language defined by the regular expression a∗a, and Solution: An important result about a deterministic finite automaton M = (Q,Σ, δ, s, F)
[PDF] CSE 105, Fall 2019 - Homework 2 Solutions - UCSD CSE
Key ConceptsDeterministic finite automata (DFA), state diagram, computation trace, accept / reject, language of an automaton, regular language, union of
[PDF] deterministic finite automata vs nondeterministic
[PDF] deus ex machina
[PDF] deux cent millions en chiffre
[PDF] deux mille dollars orthographe
[PDF] deux ministres de louis xiv.
[PDF] deux vecteurs colineaires def
[PDF] deuxième principe de la thermodynamique
[PDF] deuxieme vague coronavirus france
[PDF] deuxieme vague covid 19 france
[PDF] deuxieme vague covid france
[PDF] dev47apps
[PDF] developer apple com support duns
[PDF] developer ebay sign in
[PDF] developing a dialogue communication skills
1 Introducing Finite Automata
1.1 Problems and Computation
Decision Problems
Decision Problems
Given input, decide \yes" or \no"
Examples:Isxan even number? Isxprime? Is there a path fromstotin graphG? i.e., Compute a boolean function of inputGeneral Computational Problem
In contrast, typically a problem requires computing some non-boolean function, or carrying out an interactive/reactive computation in a distributed environment Examples:Find the factors ofx. Find the balance in account numberx. In this course, we will study decision problems because aspects of computability are captured by this special class of problemsWhat Does a Computation Look Like? Some code (a.k.a.control): the same for all instances The input (a.k.a. problem instance): encoded as a string over a nite alphabet As the program starts executing, some memory (a.k.a.state) {Includes the values of variables (and the \program counter") {State evolves throughout the computation {Often, takes more memory for larger problem instancesBut some programs do not need larger state for larger instances!1.2 Finite Automata: Informal Overview
Finite State Computation
Finite state: A xed upper bound on the size of the state, independent of the size of the input {A sequential program with no dynamic allocation using variables that take boolean values (or values in a nite enumerated data type) 1 {Ift-bit state, at most 2tpossible statesNot enough memory to hold the entire input
{\Streaming input": automaton runs (i.e., changes state) on seeing each bit of inputAn Automatic Door
Front padRear paddoorFigure 1: Top view of Door
closedopenfront neitherrear both neitherfront rear bothFigure 2: State diagram of controller Input: A stream of eventsDetails
Automaton
A nite automaton has: Finite set of states, withstart/initialandaccepting/nalstates;Transitions from one state to another on reading a symbol from the input.Computation
Start at the initial state; in each step, read the next symbol of the input, take the transition (edge)
labeled by that symbol to a new state. Acceptance/Rejection:If after reading the inputw, the machine is in a nal state thenwis accepted; otherwisewisrejected. 2 q 0q 1001 1
Figure 3: Transition Diagram of automaton
Conventions
The initial state is shown by drawing an incoming arrow into the state, with no source. Final/accept states are indicated by drawing them with a double circle.Example: ComputationOn input 1001, the computation is
1.Start in state q0. Read 1 and gotoq1.
2.Read 0 and goto q1.
3.Read 0 and goto q1.
4. Read 1 and goto q0. Sinceq0is not a nal state 1001 isrejected.On input 010, the computation is
1.Start in state q0. Read 0 and gotoq0.
2.Read 1 and goto q1.
3. Read 0 and goto q1. Sinceq1is a nal state 010 isaccepted.q 0q 1001 1 3
1.3 Applications
Finite Automata in Practice
grepThermostats
Coke Machines
Elevators
Train Track Switches
Security Properties
Lexical Analyzers for Parsers2 Formal Denitions
2.1 Deterministic Finite Automaton
Dening an Automaton
To describe an automaton, we to need to specify
What the alphabet is,
What the states are,
What the initial state is,
What states are accepting/nal, and
What the transition from each state and input symbol is. Thus, the above 5 things are part of the formal denition.Deterministic Finite AutomataFormal Denition
Denition 1.A deterministic nite automaton (DFA) isM= (Q;;;q0;F), whereQis the nite set of states
is the nite alphabet :Q!Q\Next-state" transition function 4 0 1 q 0q 0q1 q 1q 1q0Figure 5: Transition Table representation
q02Qinitial stateFQnal/accepting states
Given a state and a symbol, the next state is \determined".Formal Example of DFAExample2.q
0q 1001 1
Figure 4: Transition Diagram of DFA
Formally the automaton isM= (fq0;q1g;f0;1g;;q0;fq1g) where (q0;0) =q0(q0;1) =q1 (q1;0) =q1(q1;1) =q0Computation Denition 3.For a DFAM= (Q;;;q0;F), stringw=w1w2wk, where for eachi wi2, and statesq1;q22Q, we sayq1w!Mq2if there is a sequence of statesr0;r1;:::rksuch that r0=q1, for eachi,(ri;wi+1) =ri+1, and rk=q2. Denition 4.For a DFAM= (Q;;;q0;F) and stringw2, we sayMacceptswiq0w!Mq for someq2F.Useful Notation 5 Denition 5.For a DFAM= (Q;;;q0;F), let us dene a function^M:Q! P(Q) such that^M(q;w) =fq02Qjqw!Mq0g.We could sayMacceptswi^M(q0;w)\F6=;.
Proposition 6.For a DFAM= (Q;;;q0;F), and anyq2Q, andw2,j^M(q;w)j= 1.Acceptance/Recognition Denition 7.Thelanguage accepted or recognizedby a DFAMover alphabet isL(M) =fw2 jMacceptswg. A languageLis said to beaccepted/recognizedbyMifL=L(M).2.2 ExamplesExample Iq
00;1Figure 6: Automaton accepts all strings of 0s and 1s
Example II
q 0q 1011 0
Figure 7: Automaton accepts strings ending in 1
Example III
6 q 0q 1001 1 Figure 8: Automaton accepts strings having an odd number of 1s
Example IV
q 0q 1q 2q 311 1 10000
Figure 9: Automaton accepts strings having an odd number of 1s and odd number of 0s
3 Designing DFAs
3.1 General Method
Typical Problem
Problem
Given a languageL, design a DFAMthat acceptsL, i.e.,L(M) =L.Methodology Imagine yourself in the place of the machine, reading symbols of the input, and trying to determine if it should be accepted. Remember at any point you have only seen a part of the input, and you don't know when it ends. Figure out what to keep in memory.It cannot be all the symbols seen so far: it must t into a nite number of bits.73.2 Examples
Strings containing0
Problem
Design an automaton that accepts all strings overf0;1gthat contain at least one 0.Solution
What do you need to remember? Whether you have seen a 0 so far or not!q nozq zer10;10 Figure 10: Automaton accepting strings with at least one 0.Even length strings
Problem
Design an automaton that accepts all strings overf0;1gthat have an even length.Solution
What do you need to remember? Whether you have seen an odd or an even number of symbols.q eq o0;10;1Figure 11: Automaton accepting strings of even length.Pattern Recognition
Problem
Design an automaton that accepts all strings overf0;1gthat have 001 as a substring, whereuis a substring ofwif there arew1andw2such thatw=w1uw2.Solution
What do you need to remember? Whether you
haven't seen any symbols of the pattern 8 have just seen 0 have just seen 00 have seen the entire pattern 001Pattern Recognition Automaton q q 0q 00q p1 0 10010;1Figure 12: Automaton accepting strings having 001 as substring.
grepProblemProblem
Given textTand strings, doessappear inT?
Nave Solution
=s?z}|{ =s?z}|{ =s?z}|{ =s?z}|{ =s?z}|{ T1T2T3:::TnTn+1:::Tt
Running time =O(nt), wherejTj=tandjsj=n.grepProblemSmarter Solution
Solution
Build DFAMforL=fwjthere areu;v s:t: w=usvg
RunMon textT
Time = time to buildM+O(t)!
Questions
9IsLregular no matter whatsis?
If yes, canMbe built \eciently"?
Knuth-Morris-Pratt (1977): Yes to both the above questions.MultiplesProblem
Design an automaton that accepts all stringswoverf0;1gsuch thatwis the binary representation of a number that is a multiple of 5.Solution
What must be remembered? The remainder when divided by 5.How do you compute remainders?
Ifwis the numbernthenw0 is 2nandw1 is 2n+ 1.
(a:b+c) mod 5 = (a:(bmod 5) +c) mod 5 e.g.1011 = 11 (decimal)1 mod 5 10110 = 22 (decimal)2 mod 5 10111 = 23 (decimal)3 mod 5Automaton for recognizing Multiples
q 0q 1q 4q 2q 30101 1 010 0 1 Figure 13: Automaton recognizing binary numbers that are multiples of 5.