[LAC] Proving languages not to be regular

Are there non-regular languages?

The regular languages are those that can be recognized by finite automata; i.e. machines with finite memory.
Are there languages that are not regular?
Yes! One example:
enter image description here

So, how can we tell if a language is regular or not?
We use pumping lemma to tell!

Pumping lemma

Formal statement

Let L be a regular language, then there exists an integer n >= 1 depending only on L such that every string w in L of length at least n(n is called the “pumping length”) can be written as w = xyz, satisfying the following conditions:
1. |y| >= 1;
2. |xy| <= n
3. for all k >=0, x y^k z ∈ L

what does y mean?

y is the substring that can be pumped(removed or repeated any number of times, and the resulting string is always in L)
1. means the loop y to be pumped must be of length at least one.
2. means the loop must occur within the first n characters(|x| must be smaller than n)
Below is a formal expression of the pumping lemma:
enter image description here

Use of the lemma

The pumping lemma is often used to prove that a particular language is non-regular: a proof by contradiction will be used to proof that.

Proof of the pumping lemma

enter image description here
Above is a relationship between the states in pumping lemma.
Now, consider what happens if the automaton A receives the input x y^k z.
If k = 0; then the automaton goes from the start state q0(which is also p0) to pi on input x. Since pi is also pj, it must be that A goes from pi to the accepting state shown in image above. Thus, A accept xz.
If k > 0; then A goes from q0 to pi on input x, circle from pi to pi k times on input y^k, and then goes to the accepting state on input z. Thus, for any k>=0, x y^k z is also accepted by A.

Application/Example

Problem: Prove that L = {a^i b^i | i ≥ 0} is not regular.
Solution:
enter image description here

Example 2 (more challenging)

Problem: Prove that L = {0^n| n is a prefect square}.
Solution: let n be the constant in pumping-lemma.
And w = 0^n^2.
So there will be n^2 0’s.
When we write w = xyz, we can conduct that y is 1 to n 0’s
so if we make one loop ahead, xyyz will have (n^2)+1 to (n^2+n) 0’s
(because xyz is n^2 0’s and it adds a y)
However, Since the next perfect square after n^2 is(n+1)^2 =n^2 +2n+1, we know that the length of xyyz lies strictly between the consecutive perfect squares n2 and (n+1)2.
Thus, the length of xyyz cannot be a perfect square.

评论

发表评论

此博客中的热门博文

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