Non-regular languages, Theory of Computation

Suppose A = (Q,Σ, T, q0, F) is a DFA and that Q = {q0, q1, . . . , qn-1} includes n states. Thinking of the automaton in terms of its transition graph, a string x is recognized by the automaton iff there is a path through the graph from q0 to some qf ∈ F that is labeled x, i.e., if δ(q0, x) ∈ F. Suppose x ∈ L(A) and |x| = l. Then there is a path l edges long from q0 to qf . Since the path traverses l edges, it must visit l + 1 states.

756_Non-Regular Languages.png

Suppose, now, that l ≥ n. Then the path must visit at least n+1 states. But there are only n states in Q; thus, the path must visit at least one state at least twice. (This is an application of the pigeon hole principle: If one places k objects into n bins, where k > n, then at least one bin must contain at least two objects.)

1213_Non-Regular Languages1.png

Thus, whenever |x| ≥ n the path labeled w will have a cycle. We can break the path into three segments: x = uvw, where

• there is a path (perhaps empty) from q0 to p labeled u (i.e., δ(q0, u) = p),

• there is a (non-empty) path from p to p (a cycle) labeled v (i.e., δ(p, v) = p),

• there is a path (again, possibly empty) from p to qf labeled w (i.e., δ(p,w) = qf ).

But if there is a path from q0 to p labeled u and one from p to qf labeled w then there is a path from q0 to qf labeled uw in which we do not take the loop labeled v, which is to say uw ∈ L(A). Formally

δ(q0, uvvw) = δ(δ(q0, u), w) =  δ(p, w) = qf =  F

Similarly, we can take the v loop more than once:

δ(q0, uvvw) = δ(δ(δ(δ(q0, u), v), v),w)
= δ(δ(δ(p, v), v),w)

= δ(δ(p, v),w)

= δ(p,w) = qf ∈ F.

In fact, we can take it as many times as we like. Thus, uvi

w ∈ L(A) for all i.

This implies, then, that if the language recognized by a DFA with n states includes a string of length at least n then it contains in?nitely many closely related strings as well. We can strengthen this by noting (as a consequence of the pigeon hole principle again) that the length of the path from q0 to the ?rst time a state repeats (i.e., the second occurrence of p) must be no greater than n. Thus |uv| ≤ n.

Posted Date: 3/21/2013 1:37:55 AM | Location : United States







Related Discussions:- Non-regular languages, Assignment Help, Ask Question on Non-regular languages, Get Answer, Expert's Help, Non-regular languages Discussions

Write discussion on Non-regular languages
Your posts are moderated
Related Questions
Exercise:  Give a construction that converts a strictly 2-local automaton for a language L into one that recognizes the language L r . Justify the correctness of your construction.

When we say "solved algorithmically" we are not asking about a speci?c programming language, in fact one of the theorems in computability is that essentially all reasonable program

While the SL 2 languages include some surprisingly complex languages, the strictly 2-local automata are, nevertheless, quite limited. In a strong sense, they are almost memoryless

examples of decidable problems

For example, the question of whether a given regular language is positive (does not include the empty string) is algorithmically decidable. "Positiveness Problem". Note that

draw pda for l={an,bm,an/m,n>=0} n is in superscript

The SL 2 languages are speci?ed with a set of 2-factors in Σ 2 (plus some factors in {?}Σ and some factors in Σ{?} distinguishing symbols that may occur at the beginning and en

A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string ove

a) Let n be the pumping lemma constant. Then if L is regular, PL implies that s can be decomposed into xyz, |y| > 0, |xy| ≤n, such that xy i z is in L for all i ≥0. Since the le

We saw earlier that LT is not closed under concatenation. If we think in terms of the LT graphs, recognizing the concatenation of LT languages would seem to require knowing, while