Theory of computing, part 3



Download 31.07 Kb.
Date03.05.2017
Size31.07 Kb.
  • 1
  • Introduction
  • 2
  • Theoretical background Biochemistry/molecular biology
  • 3
  • Theoretical background computer science
  • 4
  • History of the field
  • 5
  • Splicing systems
  • 6
  • P systems
  • 7
  • Hairpins
  • 8
  • Detection techniques
  • 9
  • Micro technology introduction
  • 10
  • Microchips and fluidics
  • 11
  • Self assembly
  • 12
  • Regulatory networks
  • 13
  • Molecular motors
  • 14
  • DNA nanowires
  • 15
  • Protein computers
  • 16
  • DNA computing - summery
  • 17
  • Presentation of essay and discussion
  • Course outline

Finite automata

Introduction

  • Introduction
  • Deterministic finite automata (DFA’s)
  • Non-deterministic finite automata (NFA’s)
  • NFA’s to DFA’s
  • Simplifying DFA’s
  • Regular expressions  finite automata
  • Outline
  • Consider the control system for a one-way swinging door:
  • There are two states: Open and Closed
  • It has two inputs, person detected at position A and person detected at position B
  • If the door is closed, it should open only if a person is detected at A but not B
  • Door should close only if no one is detected
  • A
  • B
  • Automatic one way door
  • Open
  • Closed
  • A, no B
  • No A or B
  • A and B
  • A, no B
  • B, no A
  • A and B
  • B, no A
  • No A or B
  • Control schematic

A finite automaton is usually represented like this as a directed graph

  • A finite automaton is usually represented like this as a directed graph
  • Two parts of a directed graph:
  • The states (also called nodes or vertices)
  • The edges with arrows which represent the allowed transitions
  • One state is usually picked out as the starting point
  • For so-called ‘accepting automata,’ some states are chosen to be final states
  • Finite automaton
  • The input data are represented by a string over some alphabet and it determines how the machine progresses from state to state.
  • Beginning in the start state, the characters of the input string cause the machine to change from one state to another.
  • Accepting automata give only yes or no answers, depending on whether they end up in a ‘final state.’ Strings which end in a final state are accepted by the automaton.
  • Strings and automata

The labeled graph in the figure above represents a FA over the alphabet Σ = {a, b} with start state 0 and final state 3. Final states are denoted by a double circle.

  • Example

The previous graph was an example of a deterministic finite automatonevery node had two edges (a and b) coming out

  • The previous graph was an example of a deterministic finite automatonevery node had two edges (a and b) coming out
  • A DFA over a finite alphabet Σ is a finite directed graph with the property that each node emits one labeled edge for each distinct element of Σ.
  • Deterministic finite automata (DFA’s)

A DFA accepts a string w in Σ* if there is a path from the start state to some final state such that w is the concatenation of the labels on the edges of the path.

  • A DFA accepts a string w in Σ* if there is a path from the start state to some final state such that w is the concatenation of the labels on the edges of the path.
  • Otherwise, the DFA rejects w .
  • The set of all strings accepted by a DFA M is called the language of M and is denoted by
  • L(M)
  • More formally

Construct a DFA to recognize the regular languages represented by the regular expression (a + b)* over alphabet Σ = {a, b}.

  • Construct a DFA to recognize the regular languages represented by the regular expression (a + b)* over alphabet Σ = {a, b}.
  • This is the set {a, b}* of all strings over {a, b}. This can be recognised by
  • Example: (a+b)*

Find a DFA to recognize the language represented by the regular expression a(a + b)* over the alphabet Σ = {a, b}.

  • Find a DFA to recognize the language represented by the regular expression a(a + b)* over the alphabet Σ = {a, b}.
  • This is the set of all strings in Σ* which begin with a. One possible DFA is:
  • Example: a(a+b)*

Build a DFA to recognize the regular language represented by the regular expression (a + b)*abb over the alphabet Σ = {a, b}.

  • Build a DFA to recognize the regular language represented by the regular expression (a + b)*abb over the alphabet Σ = {a, b}.
  • The language is the set of strings that begin with anything, but must end with the string abb.
  • Effectively, we’re looking for strings which have a particular pattern to them
  • Example: pattern recognition
  • The diagram below shows a DFA to recognize this language.
  • If in state 1: the last character was a
  • If in state 2 : the last two symbols were ab
  • If in state 3: the last three were abb
  • Solution: (a+b)*abb

State transition function

  • We can also represent a DFA by a state transition function, which we'll denote by T, where any state transition of the form
  • is represented by: T(i,a) = j
  • To describe a full DFA we need to know:
  • what states there are,
  • which are the start and final ones,
  • the set of transitions between them.
  • State transition function

The class of regular languages is exactly the same as the class of languages accepted by DFAs!

  • The class of regular languages is exactly the same as the class of languages accepted by DFAs!
  • Kleene (1956)
  • For any regular language, we can find a DFA which recognizes it!
  • Regular languages

DFA’s are very often used for pattern matching, e.g. searching for words/structures in strings

  • DFA’s are very often used for pattern matching, e.g. searching for words/structures in strings
  • This is used often in UNIX, particularly by the grep command, which searches for combinations of strings and wildcards (*, ?)
  • grep stands for Global (search for) Regular Expressions Parser
  • DFA’s are also used to design and check simple circuits, verifying protocols, etc.
  • They are of use whenever significant memory is not required
  • Applications of DFA’s

DFA’s are called deterministic because following any input string, we know exactly which state its in and the path it took to get there

  • DFA’s are called deterministic because following any input string, we know exactly which state its in and the path it took to get there
  • For NFA’s, sometimes there is more than one direction we can go with the same input character
  • Non-determinism can occur, because following a particular string, one could be in many possible states, or taken different paths to end at the same state!
  • Non-deterministic finite automata

A non-deterministic finite automaton (NFA) over an alphabet Σ is a finite directed graph with each node having zero or more edges,

  • A non-deterministic finite automaton (NFA) over an alphabet Σ is a finite directed graph with each node having zero or more edges,
  • Each edge is labelled either with a letter from Σ or with .
  • Multiple edges may be emitted from the same node with the same label.
  • Some letters may not have an edge associated with them. Strings following such paths are not recognised.
  • NFA’s

If an edge is labelled with the empty string , then we can travel the edge without consuming an input letter. Effectively we could be in either state, and so the possible paths could branch.

  • If an edge is labelled with the empty string , then we can travel the edge without consuming an input letter. Effectively we could be in either state, and so the possible paths could branch.
  • If there are two edges with the same label, we can take either path.
  • NFA’s recognise a string if any one of its many possible states following it is a final state
  • Otherwise, it rejects it.
  • Non-determinism
  • DFA for a*a :
  • Why is the top an NFA while the bottom is a DFA?
  • NFA for a*a :
  • NFA’s versus DFA’s

Draw two NFAs to recognize the language of the regular expression ab + a*a.

  • Draw two NFAs to recognize the language of the regular expression ab + a*a.
  • This NFA has a  edge, which allows us to travel to state 2 without consuming an input letter.
  • The upper path corresponds to ab and the lower one to a*a
  • Example
  • This NFA also recognizes the same language. Perhaps it's easier to see this by considering the equality
  • ab + a*a = ab + aa*
  • An equivalent NFA

Since there may be non-determinism, we'll let the values of this function be sets of states.

  • Since there may be non-determinism, we'll let the values of this function be sets of states.
  • For example, if there are no edges from state k labelled with a, we'll write
  • T(k, a) = 
  • If there are three edges from state k, all labelled with a, going to states i, j and k, we'll write 
  • T(k, a) = {i, j, k}
  • NFA transition functions

All digital computers are deterministic; quantum computers may be another story!

  • All digital computers are deterministic; quantum computers may be another story!
  • The usual mechanism for deterministic computers is to try one particular path and to backtrack to the last decision point if that path proves poor.
  • Parallel computers make non-determinism almost realizable. We can let each process make a random choice at each branch point, thereby exploring many possible trees.

The class of regular languages is exactly the same as the class of languages accepted by NFAs!

  • The class of regular languages is exactly the same as the class of languages accepted by NFAs!
  • Rabin and Scott (1959)
  • Just like for DFA’s!
  • Every NFA has an equivalent DFA which recognises the same language.
  • Some facts

We prove the equivalence of NFA’s and DFA’s by showing how, for any NFA, to construct a DFA which recognises the same language

  • We prove the equivalence of NFA’s and DFA’s by showing how, for any NFA, to construct a DFA which recognises the same language
  • Generally the DFA will have more possible states than the NFA. If the NFA has n states, then the DFA could have as many as 2n states!
  • Example: NFA has three states {A}, {B}, {C}
  • the DFA could have eight: {}, {A}, {B}, {C},
  • {A, B}, {A, C}, {B, C}, {A, B, C}
  • These correspond to the possible states the NFA could be in after any string
  • From NFA’s to DFA’s

Begin in the NFA start state, which could be a multiple state if its connected to any by 

  • Begin in the NFA start state, which could be a multiple state if its connected to any by 
  • Determine the set of possible NFA states you could be in after receiving each character. Each set is a new DFA state, and is connected to the start by that character.
  • Repeat for each new DFA state, exploring the possible results for each character until the system is closed
  • DFA final states are any that contain a NFA final state
  • DFA construction

The start state is A, but following an a you could be in A or B; following a b you could only be in state A

  • The start state is A, but following an a you could be in A or B; following a b you could only be in state A
  • A
  • B
  • C
  • a
  • b
  • a,b
  • A
  • A,B
  • a
  • b
  • b
  • A,C
  • a
  • b
  • a
  • NFA
  • DFA
  • Example (a+b)*ab

Regular expressions represent the regular languages.

  • Regular expressions represent the regular languages.
  • DFA’s recognize the regular languages.
  • NFA’s also recognize the regular languages.
  • Summary

So far, we’ve introduced two kinds of automata: deterministic and non-deterministic.

  • So far, we’ve introduced two kinds of automata: deterministic and non-deterministic.
  • We’ve shown that we can find a DFA to recognise anything language that a given NFA recognises.
  • We’ve asserted that both DFA’s and NFA’s recognise the regular languages, which themselves are represented by regular expressions.
  • We prove this by construction, by showing how any regular expression can be made into a NFA and vice versa.
  • Finite automata

Given a regular expression, we can find an automata which recognises its language.

  • Given a regular expression, we can find an automata which recognises its language.
  • Start the algorithm with a machine that has a start state, a single final state, and an edge labelled with the given regular expression as follows:
  • Regular expressions  finite automata

If an edge is labelled with , then erase the edge.

  • If an edge is labelled with , then erase the edge.
  • Transform any diagram like
  • into the diagram
  • Four step algoritm

3. Transform any diagram like

  • 3. Transform any diagram like
  • into the diagram
  • Four step algoritm

4. Transform any diagram like

  • 4. Transform any diagram like
  • into the diagram
  • Four step algoritm

Construct a NFA for the regular expression,

  • Construct a NFA for the regular expression,
  • a* + ab
  • Start with
  • Apply rule 2
  • a* + ab
  • ab
  • a*
  • Example a*+ab
  • ab
  • a
  • a
  • a
  • b
  • Apply rule 4 to a*
  • Apply rule 3 to ab
  • Example a*+ab

1 Create a new start state s, and draw a new edge labelled with  from s to the original start state.

  • 1 Create a new start state s, and draw a new edge labelled with  from s to the original start state.
  • 2 Create a new final state f, and draw new edges labelled with  from all the original final states to f
  • Finite automata  regular expressions

3 For each pair of states i and j that have more than one edge from i to j, replace all the edges from i to j by a single edge labelled with the regular expression formed by the sum of the labels on each of the edges from i to j.

  • 3 For each pair of states i and j that have more than one edge from i to j, replace all the edges from i to j by a single edge labelled with the regular expression formed by the sum of the labels on each of the edges from i to j.
  • 4 Construct a sequence of new machines by eliminating one state at a time until the only states remaining are s and the f.
  • Finite automata  regular expressions

As each state is eliminated, a new machine is constructed from the previous machine as follows:

  • As each state is eliminated, a new machine is constructed from the previous machine as follows:
    • Let old(i,j) denote the label on edge i,j of the current machine. If no edge exists, label it .
    • Assume that we wish to eliminate state k. For each pair of edges i,k (incoming edge) and k,j (outgoing edge) we create a new edge label new(i, j)
  • Eliminating states

The label of this new edge is given by:

  • The label of this new edge is given by:
  • new(i,j) = old(i,j) + old(i, k) old(k, k)* old(k,j)
  • All other edges, not involving state k, remain the same:
  • new(i, j) = old(i, j)
  • After eliminating all states except s and f, we wind up with a two-state machine with the single edge s, f labelled with the desired regular expression new(s, f)
  • Eliminate state k
  • Initial DFA
  • Steps 1 and 2
  • Add start and final states
  • Example
  • Eliminate state 2
  • (No path to f)
  • Eliminate state 0
  • Eliminate state 1
  • Final regular expression
  • Example

Sometimes our constructions lead to more complicated automata than we need, having more states than are really necessary

  • Sometimes our constructions lead to more complicated automata than we need, having more states than are really necessary
  • Next, we look for ways of making DFA’s with a minimum number of states
  • Myhill-Nerode theorem:
  • ‘Every regular expression has a unique* minimum state DFA’
  • * up to a simple renaming of the states
  • Finding simpler automata

Two steps to minimizing DFA:

  • Two steps to minimizing DFA:
  • 1 Discover which, if any, pairs of states are indistinguishable. Two states, s and t, are equivalent if for all possible strings w, T(s,w) and T(t,w) are both either final or non-final.
  • 2 Combine all equivalent states into a single state, modifying the transition functions appropriately.
  • Finding minimum state DFA

States 1 and 2 are indistinguishable! Starting in either, b* is rejected and anything with a in it is accepted.

  • States 1 and 2 are indistinguishable! Starting in either, b* is rejected and anything with a in it is accepted.
  • a
  • a
  • b
  • b
  • a
  • b
  • 1
  • 2
  • a,b
  • a
  • a,b
  • a,b
  • b
  • Consider the DFA

Remove all inaccessible states, where no path exists to them from start.

  • Remove all inaccessible states, where no path exists to them from start.
  • Construct a grid of pairs of states.
  • Begin by marking those pairs which are clearly distinguishable, where one is final and the other non-final.
  • Next eliminate all pairs, which on the same input, lead to a distinguishable pair of states. Repeat until you have considered all pairs.
  • The remaining pairs are indistinguishable.
  • Part 1, finding indistinguishable pairs

Construct a new DFA where any pairs of indistinguishable states form a single state in the new DFA.

  • Construct a new DFA where any pairs of indistinguishable states form a single state in the new DFA.
  • The start state will be the state containing the original start state.
  • The final states will be those which contain original final states.
  • The transitions will be the full set of transitions from the original states (these should all be consistent.)
  • Part 2, construct minimum DFA
  • a
  • a
  • a,b
  • a
  • a
  • b
  • b
  • b
  • 0
  • 3
  • 2
  • 1
  • 4
  • What are the distinguishable pairs of states?
  • Clearly, {0, 4} {1, 4} {2, 4} {3, 4} are all distinguishable because 4 is final but none of the others are.
  • b
  • Example

We eliminate these as possible indistinguishable pairs.

  • We eliminate these as possible indistinguishable pairs.
  • Next consider {0, 1}. With input a, this becomes {3, 4} which is distinguishable, so {0, 1} is as well.
  • Similarly, we can show {0, 2} and {0, 3} are also distinguishable, leading to the modified grid…
  • 1
  • 2
  • 3
  • 4
  • ?
  • ? ?
  • ? ? ?
  • x x x x
  • 0 1 2 3
  • 1
  • 2
  • 3
  • 4
  • x
  • x ?
  • x ? ?
  • x x x x
  • 0 1 2 3
  • Grid of pairs of state

We are left with

  • We are left with
  • {1, 2} given a {4, 4}
  • given b {2, 1}
  • {2, 3} given a {4, 4}
  • given b {1, 2}
  • {1, 3} given a {4, 4}
  • given b {2, 2}
  • These do not lead to pairs we know to be distinguishable, and are therefore indistinguishable!
  • Remaining pairs

States 1, 2, and 3 are all indistinguishable, thus the minimal DFA will have three states:

  • States 1, 2, and 3 are all indistinguishable, thus the minimal DFA will have three states:
  • {0} {1, 2, 3} {4}
  • Since originally T(0, a) = 3 and T(0, b) = 1, the new transitions are T(0, a) = T(0, b) = {1,2,3}
  • Similarly,
  • T({1,2,3}, a) = 4 and T({1,2,3}, b) = {1,2,3}
  • Finally, as before,
  • T(4, a) = 4 and T(4, b) = 4
  • Construct minimal DFA

The resulting DFA is much simpler:

  • The resulting DFA is much simpler:
  • a
  • a,b
  • a,b
  • b
  • 0
  • 1, 2, 3
  • 4
  • This recognises regular expressions of the form, (a + b) b* a (a + b)*
  • This is the simplest DFA which will recognise this language!
  • Resulting minimal DFA

We now have many equivalent ways of representing regular languages: DFA’s, NFA’s, regular expressions and regular grammars.

  • We now have many equivalent ways of representing regular languages: DFA’s, NFA’s, regular expressions and regular grammars.
  • We can also now simply(?!) move between these various representations.
  • We’ll see next lecture that the automata representation leads to a simple way of recognising some languages which are not regular.
  • We’ll also begin to consider more powerful language types and correspondingly more powerful computing models!
  • conclusions

M = (Q, Σ, δ, q0, F)

  • M = (Q, Σ, δ, q0, F)
  • Q = states a finite set
  • Σ = alphabet a finite set
  • δ = transition function a total function in Q  Σ  Q
  • q0 = initial/starting state q0  Q
  • F = final states F  Q
  • Formal definition


Download 31.07 Kb.

Share with your friends:




The database is protected by copyright ©sckool.org 2020
send message

    Main page