3
$\begingroup$

For a language L $\subseteq$ $\Sigma$* , define LOG(L) = { u $\epsilon$ $\Sigma$* | $\exists$ v s.t. |v| = $2^|$$^u$$^|$ and uv $\epsilon$ L}. Show that if L is regular so is LOG(L).


I was trying to come up with some finite state automaton for LOG(L) but can't find any. Please give some hint.

$\endgroup$
3
  • 1
    $\begingroup$ You seem to be confusing u and v. Should it be “exists v”? $\endgroup$ Commented Sep 22, 2019 at 13:55
  • $\begingroup$ Yeah it is "exists v" edited it $\endgroup$ Commented Sep 23, 2019 at 3:37
  • $\begingroup$ I think your problem is not creating the finite state automaton, it is finding out something about the possible lengths of strings in L. Try showing that LOG(L) = "prefixes of strings in L which have a certain length". $\endgroup$
    – gnasher729
    Commented Sep 23, 2019 at 4:23

1 Answer 1

0
$\begingroup$

Yes, it is regular. It is complicated.

Create an FSA for L.

For each pair of states (Si, Sj) find the set of possible counts of symbols that could lead from Si to Sj. This set can be described in a finite way, it has the form of some constants ci, plus if there is a cycle involved, n*k + di for some fixed k and some constants di, and all n ≥ 0. Example: If you can get from state S3 back to S3 with a cycle of length 3 and another cycle of length 5, then the number of symbols processed is (0, 3, 5, 6, n*1 + 8).

For each state Si, find the possible set of possible counts of symbols that could reach an accepting state.

Since we accept strings of length k when L contains a string of length k + 2^k, we can now determine the possible numbers of symbols processed to enter state Si, which would lead to an accepted string of length k + 2^k.

So we have the same FSA, but it needs to accept a string in state Si if we have entered Si with the right number of symbols.

We then modify the FSA so you can enter a state Si only with the right number of symbols, and that's it.

$\endgroup$
1
  • $\begingroup$ "We then modify the FSA so you can enter a state Si only with the right number of symbols" How? $\endgroup$
    – xskxzr
    Commented Sep 23, 2019 at 9:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.