1
$\begingroup$

I'm working on proving that the following language is regular:

B = {x|for some y, length(x) = length(y) and xy are in A}

where A is a regular language.

Since A is regular, we know that there is an FSA that describes it. My plan is to modify this FSA, M, into M' using jumps, to prove that for certain strings of x, that it is possible/not possible to land in an accept state. However, the empty string has a length of 0 and so I'm confused as to how to go about this.

Any help would be appreciated! Thank you!

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Note that, although this language is not one of the four in the question @YuvalFilmus links to, it is covered in his answer to that question. $\endgroup$
    – David Richerby
    Oct 5, 2015 at 6:59
  • $\begingroup$ If you can use closure properties of regular languages, you could start by finding $A'=A \cap \{x^n \;|\; n \mod 2 = 0\}$, i.e. a language of all words of even length. $A'$ would be regular due to closure under intersection. Then $B$ would be regular due to closure under left quotient. $\endgroup$
    – wvxvw
    Oct 5, 2015 at 10:26
  • 1
    $\begingroup$ @wvxvw, I don't follow. Left quotient with what? Presumably you want the left quotient $C\backslash A'$, but with what choice of language $C$? $\endgroup$
    – D.W. ♦
    Oct 5, 2015 at 16:16
  • $\begingroup$ @D.W. Ummm, yes, I see the problem now. But if one was determined to go that way, then it's still possible. Since the set of all prefixes of a regular language is finite, we can choose only those prefixes which are half the length of the world and then union them to get $C$. $\endgroup$
    – wvxvw
    Oct 5, 2015 at 18:04
  • $\begingroup$ @wvxvw, yeah, I thought of that, but I don't see how to make that approach work. Let's say $A$ has some words of length 4 and some words of length 10. It sounds like we'll end up with $C$ containing some words of length 2 and some words of length 5. But then the left quotient $C\backslash A$ may contain words of length 2, 5, and 8, instead of only length 2 and 5 (as desired) -- i.e., the left quotient may contain some spurious words of length 8. $\endgroup$
    – D.W. ♦
    Oct 5, 2015 at 18:17

0

Reset to default

Browse other questions tagged or ask your own question.