for every regular language there is a constant n


For every regular language there is a constant n depending only on L such that, for all strings x ∈ L if |x| ≥ n then there are strings u, v and w such that

1. x = uvw,

2. |uv| ≤ n,

3. |v| ≥ 1,

4. for all i ≥ 0, uviw ∈ L.

What this says is that if there is any string in L "long enough" then there is some family of strings of related form that are all in L, that is, that there is some way of breaking the string into segments uvw for which uvi w is in L for all i. It does not say that every family of strings of related form is in L, that uvi w will be in L for every way of breaking the string into three segments uvw.

Request for Solution File

Ask an Expert for Answer!!
Theory of Computation: for every regular language there is a constant n
Reference No:- TGS0217954

Expected delivery within 24 Hours