Author |
Topic: RegEx: half(L) (Read 6842 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
RegEx: half(L)
« on: Feb 24th, 2003, 2:49pm » |
 Quote  Modify
|
A very hard problem. Let L be a regular language. Show that the following language is regular.
half(L) = { x : there exists a y such that xy is in L, and |x| = |y|}
Hint 1: It will be probably be too difficult to construct a RegEx for this. Try making a nondeterministic finite automaton. If you're not aware of it, there's a one-to-one correspondence between deterministic finite automata (DFA), and nondeterministic finite automata (NFA). This is surprising because one would expect nondeterminism to give us much added power, but it ends up being no better than a DFA.
Hint 2: Think about cross products. If you've ever seen the product construction based proof that regular languages are closed under intersection, that style of approach should be helpful for this problem.
|
| « Last Edit: Feb 24th, 2003, 6:49pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
DH
Guest
|
Consider the DFA for L. For each state there are a finite number of paths ( from the initial state to this state ) that do not contain loops and in the DFA there are a finite number of basic loops. Each path can be decomposed in a path without loops and a number of basic loops so the length of each path can be expressed as :
K+A1*L1+A2*L2 ... An*Ln
where K is the length of the path without loops , L1 ... Ln are the lengths of the loops and A1 ... An the times each loop is taken.
The lengths of all suffixes that can be generated from a certain state ( S ) belong to the following set:
{ K1+A1_1*L1_1+A1_2*L1_2 ... A1_n1*L1_n1 | 0<=A1_1,A1_2 ... A1_n1 } U
{ K2+A2_1*L2_1+A2_2*L2_2 ... A2_n2*L2_n2 | 0<=A2_1,A2_2 ... A2_n2 } U
....................
{ Km+Am_1*Lm_1+Am_2*Lm_2 ... Am_nm*Lm_nm | 0<=Am_1,Am_2 ... Am_nm }
Where Ki are the lengths of all unique paths that do not contain loops and that start with S and end with an accepting state, Li_1 ... Li_ni are the lengths of the loops that can be used when walking along the respective path and Ai_1 ... Ai_ni are the times each loop is taken.
For each state we have a set of possible lengths for the prefixes that lead to that state and a set of possible lengths for the suffixes that can be generated starting form that state.Every set can be expressed as a finite union : U { K'i+A*L } where L is a multiple for every Li_j and 0<=A. For numbers greater than the maximum of all K'i constants the set is clearly periodic.
Every number in the set is a valid prefix/suffix length and every valid length is in the set.
For each state we can compute the prefix set and the suffix set. The sets have the same period L and we can express them using the same maximum constant ( just take the maximum from all constants in all sets ).
For Half(L) we construct a new DFA that encodes in the states the length of the prefix if the length is <= maximum_constant or the length modulo L otherwise. To find the accepting states we compute the suffix lengths set. For prefix lengths <= maximum_constant we check the constant lengths and for lengths >maximum constant we check
the periodic part of the set.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
Since I find DH's solution quite hard to understand  I'll address the problem in another way:
Lets suppose that A is a DFA for L ( A = (Q, [sum], q0, [delta], F)1).
First, in a non-deterministic way (i.e. using [epsilon] traversals) we will find the state (q) which is the state that is reached after X is run by A (see the figure below).
Second, each Aq will simulate a parallel run (i.e. a cross-product automatum) on X from q0 to q and on some Y from q to some accepting state. Formaly, Aq = (Q*Q, [sum], [q0,q], [delta]q, {q}*F) where [delta]q([qi, qj], a) = {[[delta](qi, a), [delta](qj, b)] | b[in][sum]}
1 Q stands for the (finite) states set.
[sum] stands for the (finite) symbol set that can be used.
q0 stands for the initial state.
[delta] stands for the transition function (Q*[sum] -> Q).
F stands for the accepting states set.
Hopes that this answer is more easy to understand... 
Please feel free to ask any question if you do not undertand the above...
|
|
IP Logged |
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: RegEx: half(L)
« Reply #3 on: Oct 27th, 2003, 8:53am » |
Quote Modify
|
Wow ! Finally a reply 
I must agree that your solution is much more elegant. My solution is harder to understand but this is mainly because it's poorly worded 
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: RegEx: half(L)
« Reply #4 on: Oct 27th, 2003, 9:13am » |
Quote Modify
|
on Oct 27th, 2003, 8:53am, DH wrote:Wow ! Finally a reply
I must agree that your solution is much more elegant. My solution is harder to understand but this is mainly because it's poorly worded |
|
DH hi,
I glad that you haven't lost your persistance, waiting so long for a reply  .
I also understand that you like this kind of riddles, so I'll post a similer one in a while  ...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove