question on proving a language is regular
- From: TheGist <thegist@xxxxxxxxxx>
- Date: Sun, 14 Jan 2007 19:12:54 -0500
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?
My thoughts so far are to show by constructing a FA.
Suppose we have a FA, call it F that accepts L.
My FA, call it F' would be constructed by copying
F and running as follows...
F' would nondeterministically skip to the q_ith state
of the FA that accepts xy where i is the length of x, |x|.
From there the FA simply runs as normal and accepts y and thusL_x is regular.
Any advice?
Thanks!
.
- Follow-Ups:
- Re: question on proving a language is regular
- From: Chris Smith
- Re: question on proving a language is regular
- Prev by Date: a DFA for the language L={w in {0,1}*|w does not contain the substring 001}
- Next by Date: Re: a DFA for the language L={w in {0,1}*|w does not contain the substring 001}
- Previous by thread: a DFA for the language L={w in {0,1}*|w does not contain the substring 001}
- Next by thread: Re: question on proving a language is regular
- Index(es):