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
what problems are tackled under numerical integration

. On July 1, 2010, Harris Co. issued 6,000 bonds at $1,000 each. The bonds paid interest semiannually at 5%. The bonds had a term of 20 years. At the time of issuance, the market r

Computation of a DFA or NFA without ε-transitions An ID (q 1 ,w 1 ) computes (qn,wn) in A = (Q,Σ, T, q 0 , F) (in zero or more steps) if there is a sequence of IDs (q 1

1. Simulate a TM with infinite tape on both ends using a two-track TM with finite storage 2. Prove the following language is non-Turing recognizable using the diagnolization

constract context free g ={ a^n b^m : m,n >=0 and n

examples of decidable problems

write grammer to produce all mathematical expressions in c.

Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff ≡L partitions Σ* into ?nitely many Nerode equivalence classes. Proof: For the "only if" direction (that every recogn

The k-local Myhill graphs provide an easy means to generalize the suffix substitution closure property for the strictly k-local languages. Lemma (k-Local Suffix Substitution Clo

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .