advertisement

Content of the Notes Finite Automata Deterministic Finite Automata (DFA) Deterministic Finite Automata: Example Transition Diagrams Transition Tables Extending transition function to strings Language Accepted by a DFA Nondeterministic Finite State Automata (NFA) Extending transition function to strings for NFA Language Accepted by an NFA Equivalence of DFA and NFA NFA with null transitions Definition of Extended transition Function Equivalence of Null- NFA and DFA Finite Automata Deterministic Finite Automata (DFA) A deterministic Finite Automaton consists of: • A finite set of states, often denoted by Q. • A finite set of input symbols (letters), often denoted by _. • A transition function, that takes two arguments: a state from Q and a letter from _, and returns a state. Transition function is often denoted by δ. • A starting state, q0, which is one of the states of Q. • A set F ⊆ Q of final/accepting states. A = (Q,_, δ, q0, F). Deterministic Finite Automata: Example DFA accepting strings which contain odd number of 1s (here we are taking the alphabet as {0, 1}). A = ({q0, q1}, {0, 1}, δ, q0, {q1}). δ(q0, 0) = q0. δ(q0, 1) = q1. δ(q1, 0) = q1. δ(q1, 1) = q0. Transition Diagrams • Using circles to denote states, arrows to denote transition. • Starting state is denoted by using an arrow labeled start. • Final/accepting states are denoted by using double circles. Transition Tables Extending transition function to strings Language Accepted by a DFA Nondeterministic Finite State Automata (NFA) • The transition function maps the input (state, symbol) to a set of states (a subset of Q) Example: L = {w | n-th symbol in w from the end is 1}. Extending transition function to strings for NFA Language Accepted by an NFA Examples of DFA and NFA 1. DFAs Draw Deterministic Finite Automata to accept the following sets of strings over the alphabet {0,1}: a. b. c. d. 2. NFAs All strings that contain exactly 4 "0"s. All strings ending in "1101". All strings containing exactly 4 "0"s and at least 2 "1"s. All strings whose binary interpretation is divisible by 5. Draw Non-deterministic Finite Automata with the specified number of states to accept the following sets: a. All strings containing exactly 4 "0"s or an even number of "1"s. (8 states) b. All strings such that the third symbol from the right end is a "0". (4 states) c. All strings such that some two zeros are separated by a string whose length is 4i for some i >= 0. (6 states) Equivalence of DFA and NFA A DFA is also an NFA. So, we only need to show that a language accepted by NFA is also accepted by some DFA. Suppose NFA A = (Q,_, δ, q0, F) is given. Define DFA AD = (QD,_, δD, {q0}, FD) as follows. QD = {S | S ⊆ Q}. FD = {S | S ⊆ Q and Equivalence of DFA and NFA NFA with null transitions