[LAC] Equivalence of DFA and NFA

It is a surprising fact that every language that can be described by some NFA can also be described by some DFA. Moreover, the DFA has more states than NFA. The smallest DFA can have 2^n states while the smallest NFA for the same language has only n states.

We can thus convert an NFA into a DFA by considering each possible set of NFA states as a single DFA state!

subset construction

The subset construction starts from an NFA N = (Qn, Σ, δn, q0, Fn). Its goal is the description of a DFA D = (Qd, Σ, δd, {q0}, Fd} such that L(D) = L(N).
where
δD(A)(P,x) = U{δ(q,x) | q ∈ P}
FD(A) = {P∈P(Q)|P∩F≠∅}

It might be confused if we just say its definition, i’ll show how the NFA converted to DFA.

Example

The language is same as before–accpets all strings that end in “01”
We have figured out its NFA:
enter image description here

So first, we want to write a complete subset construction of it.
So how many possible states are there in the DFA?
2^3 = 8 states, we use a transition table and write down all the states.
(notice the final or accepting states now are not just one, may be a lot)
It is a ongoing version of transition table.
enter image description here
Then we fill in the table about the result after input a symbol.
enter image description here

ok, by now, what we write is a compelete subset construction including all states

If you write these sets(notice, states are sets now) into a alphabet, we can make a new and more clear transition table:
enter image description here
Of the eight states in the above image, starting in the start state B, we can only reach state B, E and F. The other five states are inaccessible from the start state and may as well not be there. We often can avoid the exponential-time step of construction transition table entries for every subset of states if we perform “lazy evaluation” on the subsets, as follows.

  • Basis: We know for certain that the singleton set consisting only of N’s start state is accessible.
  • Induction: Suppose we have determined that set S of states is accessible; then fro each input symbol a, compute the set of states δd(S, a); we know that these sets of states will also be accessible.

In this way, we can converge the subset construction. We can draw a transition diagram by this converged transition table:
enter image description here

Example question

enter image description here

We can write out the following transition table:
enter image description here

If we simplify it:
enter image description here

评论

发表评论

此博客中的热门博文

[MLE] Linear Classification

图片
Linear Classification Discriminant functions Least squares for classification Fisher’s linear discriminant K-Nearest Neighbour(KNN) Classification What’s decision boundaries/linearly separable? The goal in classification is to take an input vector x and to assign it to one of K discrete classes \(C_k\) where k = 1,…,K. In the most common scenario, the classes are taken to be disjoint, so that each input is assigned to one and only one class. The input space is thereby divided into decision regions whose boundaries are called decision boundaries or decision surfaces. In this blog, we consider linear models for classification , by which we mean that the decision surfaces are linear functions of the input vector x and hence are defined by (D-1) -dimensional hyperplanes within the D-dimensional input space. For example: in 3D input space, the decision boundary will be a 2D surface What is Linear Separability Linearly separable data: Datasets whose classes can be separated by
阅读全文

[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
阅读全文

[CS231] Neural Networks

图片
Neural Network Table of Contents: Quick intro without brain analogies Modeling one neuron Biological motivation and connections Single neuron as a linear classifier Commonly used activation functions Neural Network architectures Layer-wise organization Summary Additional references Quick intro It is possible to introduce neural networks without appealing to brain analogies. In the section on linear classification we computed scores for different visual categories given the image using the formula \( s = W x \), where \(W\) was a matrix and \(x\) was an input column vector containing all pixel data of the image. In the case of CIFAR-10, \(x\) is a [3072x1] column vector, and \(W\) is a [10x3072] matrix, so that the output scores is a vector of 10 class scores. An example neural network would instead compute \( s = W_2 \max(0, W_1 x) \). Here, \(W_1\) could be, for example, a [100x3072] matrix transforming the image into a 100-dimensional intermediate vector. The funct
阅读全文