[LAC] Deterministic Finite Automata(DFA)

As was mentioned before, a finite automation has a set of states, and its “control” moves from state to state in response to external “inputs”

  • If the control is “deterministic”, means that the automata cannot be in more than one state at any one time.
  • “non-deterministic”, means that it may be in several states at once.

DFA

The term “deterministic” refers to the fact that on each input there is one and only one state to which the automata can transition from its current state.

A DFA consists of:

  • A finite set of states, often denoted Q
  • A finite set of input symbols, often denoted Σ
  • A transition function that takes a state and an input symbol as arguments and returns a state. The transition function will commonly be denoted δ
  • A start state, one of the states in Q

  • A set of final or accepting state F. The set F is a subset of Q.
    Five tuple notation

    A = (Q, Σ, δ, q0, F)
    where A is the name of DFA
    Q is its set of states
    Σ is its input symbols
    δ is its transition functions
    q0 is the start state
    F is its set of accepting states

How a DFA processes strings

The first things we need to understand about a DFA is how the DFA decides whether or not to “accept” a sequence of input symbols.

  • The language of DFA is the set of all strings that DFA accepts.
  • Suppose a1a2…an is the sequence of input symbols
  • we start out with DFA in its start state q0
  • we consult the transition function δ to find the state that A enters after processing the input symbol a1
  • Next…Again..until the final one an and we get the final state qn
  • If qn is a member of F, then the input a1a2…an is accepted, otherwise “rejected”

e.g. For a language:
{x01y | x and y are any strings of 0’s and 1’s}
We need to specify every components.

States

There are three states q0, q1 and q2

  • q0 is the start state. Never seen 01
  • q1 is the accepting state. Have seen 01
  • q2 is never seen 01 but the most recent input is 0(so if there is a 1 next coming in it will be q1)

transition function:

It is easy to obtain transition function
δ(q0, 1) = q0
δ(q0, 0) = q2
δ(q2, 0) = q2
δ(q2, 1) = q1
δ(q1, 0) = δ(q1, 1) = q1

So A = ({q0,q1,q2}, {0,1}, δ, q0, {q1})

Simpler notations for DFA’s

Specifying a DFA as a five tuple is tedious and hard to read.
There are two preferred notations for describing automata:

  • transition diagram
  • transition table

Transition diagram

  • For each state in Q there is a node
  • For each state q in Q and each input symbol a in Σ, let δ(q, a) = p. Then the transition diagram has an arc from node q to node p, labeled a.(a can be all the symbols if possible)
  • There is an arrow into the start state q0, labeled Start. This arrow does not originate at any node.
  • Nodes corresponding to accepting states are marked by a double circle. States not in F have a single circle.

The transition diagram of the above example:
enter image description here

Transition tables

The rows of the table correspond to the states, the columns correspond to the inputs. The entry for the row corresponding to state q and the column corresponding to input a is the state δ(q, a)

enter image description here

Extending the transition function to strings

Now, we need to make the notion of the language of a DFA precise. To do so, we define an extended transition function that describes what happens when we start in any state and follow any sequence of inputs.

  • The extended transition function constructed from δ will be called δ*(the correct one should be a hat on delta)
  • The extended transition function is a function that takes a state q and a string w and returns a state p – the state that the automata reaches when starting in state q and processing the sequence of inputs w

Basics: δ*(q, ε) = q that is, if we are in state q and read no inputs, then we are still in state q.
Induction: δ* (q, w) = δ(δ* (q, x), a) where w is a string of form xa

Example

L = {w | w has both an even number of 0’s and an even number of 1’s}

four states:
q0: both 0 and 1 are even
q1: 0 even, 1 odd
q2: 0 odd, 1 even
q3: both odd

A = ({q0, q1, q2, q3}, {0, 1}, δ, q0, {q0})
transition diagram
enter image description here
transition table
enter image description here

Suppose the input is 110101
We expect that δ*(q0, 110101) = q0
That’s how we verify the claim:
enter image description here

Now we can define DFA by
L(A) = {w | δ*(q0, w) is in F}
That is, the language of A is the set of strings w that take the start state q0 to one of the accepting states.
If L is L(A) for some DFA A, then we say L is a regular language

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If
阅读全文

[AIM] MetaHeuristics

图片
Day2 Outline Metaheuristics -definition Single point based search method(simple stochastic local search) Iterated local search Scheduling Tabu Search Metaheuristic what is a metaheuristic? A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. what is the difference between heuristic and metaheuristic? Heuristic : Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution. Metaheuristic : Meta-heuristics, on the other hand, are problem-independent techniques . As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes . In general, t
阅读全文