Re: question on proving a language is regular

In article <7zy7o4herf.fsf@xxxxxxxxxxxxx>,
torbenm@xxxxxxxxxxxxx (Torben AEgidius Mogensen) wrote:

Chris Smith <cdsmith@xxxxxxx> writes:

TheGist <thegist@xxxxxxxxxx> wrote:
L is a regular language.
L_x={y | xy in L} where x is some fixed string.

How do I show that L_x is a regular language?

Start from the DFA for L. Modify it to get a DFA for L_x. You don't
need non-determinism here at all. It's actually really simple once you
get the trick. Try a few examples, and see if you can figure it out.

An additional hint: When you have the DFA for L, try using x as input.
See what state you end in.
Hmm, maybe I am just slow today but I am not quite seeing this yet...
Just to state the obvious,
Suppose I have a DFA that accepts L. So, the first i states are fixed in
that they accept the fixed string(prefix) x. After the first i states
are traversed then begins the checking for y, but we know xy is in L so
we must go to an accept state for any y such that xy is in L.
Intuitively it seems straightforward that L_x is regular, or is my logic
wrong?
As far as Myhill-Nerode is concerned, the number of equivalence classes
of L_x is finite for more or less the same reason, that is,(somewhat
circularily) since x is a fixed prefix and xy is in L than the number of
states required to check y must be in finite, the number of states used
to check the prefix x must be finite and thus the DFA used to check xy
must obviously have a finite number of states. But this is probably the
wrong way to look at this. How else may I determine that the number of
equivalence classes of L_x is finite?
.

Relevant Pages

  • Re: Testing for acceptance of Kleene closure of alphabet
    ... so you can assume you already have that algorithm available ... We know that we can produce another DFA ... > N such that Lis the complement of L. ... > Suppose L is a regular language with alphabet SIGMA. ...
    (comp.theory)
  • Re: question on proving a language is regular
    ... L_x=where x is some fixed string. ... How do I show that L_x is a regular language? ... Start from the DFA for L. Modify it to get a DFA for L_x. ... Chris Smith ...
    (comp.theory)
  • Re: question on proving a language is regular
    ... Chris Smith writes: ... L_x=where x is some fixed string. ... How do I show that L_x is a regular language? ... Start from the DFA for L. Modify it to get a DFA for L_x. ...
    (comp.theory)