UVA CS 302 - Deterministic Finite Automata

Unformatted text preview:

cs302 Theory of Computation UVa Spring 2008Notes: Deterministic Finite AutomataThursday, 24 JanuaryUpcoming Schedule:• Monday, 2-3pm Office Hours (Olsson 236A)• Monday, 5:30-6:30 Problem-Solving Session (Olsson 226D)• Tuesday, 29 January: Problem Set 1 is due at the beginning of class• Reading for next week: Finish Chapter 1Problems and MachinesOne of the main goals in this class is to understand what set of problems can be solved bydifferent abstract machines. A complexity class is a set of problems of similar complexity.One way to define a complexity class is as the set of problems that can be solved by aspecified abstract machine. Later, we will see complexity classes that further constrain theabstract machine by limiting the time or space available as a function of the size of theproblem input.Figure 1: Complexity ClassesWhere are the problems with finite input domains in the figure?Are they any problems that can be solved by Finite Automata that cannot be solved byTuring Machine?DFA-1Definition: A finite automaton (DFA) is a 5-tuple (Q, Σ, δ, q0, F ):1. Q — a finite set (the states)2. Σ — a finite set (the alphabet)3. δ: Q×Σ → Q —- a function from a state and alphabet symbol to a state (the transitionfunction)4. q0∈ Q — the start state5. F ⊆ Q — the set of accept statesHow many start states can there be?How many accept states can there be?If we describe δ using a table, how big is the table?Q = {A, B}Σ = {0, 1}δ is described by:0 1A A BB B Aq0= AF = {B}Definition: A regular language is a language that can be recognized by some finite automa-ton.Language Recognition: L(A) represents the language recognized by DFA A:w ∈ L(A) ⇔ running A on input w ends in an accept stateComputation Model for DFADefine δ∗as the extended transition function:δ∗( , w) ∈ ⇔ w ∈


View Full Document
Download Deterministic Finite Automata
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Deterministic Finite Automata and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Deterministic Finite Automata 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?