HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Given the regular set $S = a^*ba^*ba^*$, is the set $S'$ of all first thirds of strings in S (with length divisible by 3) regular?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theallwithlengthregulardivisiblefirststringsgivenset

Problem

I have no idea how to approach this problem, could I get at least a hint on how to go about proving/disproving this?

I've tried the pumping lemma but I don't think it applies here. I've also tried reasoning about closure properties, but I think my reasoning is faulty. My thought process so far is a string (with length divisible by 3) that is in L can be denoted as a regular expression. As such, the machine M for L can be broken down into M1, M2 and M3, each a machine for handling the first, middle and last thirds of the string. M2 would therefore be the machine corresponding to J, so J is regular.

Solution

The first step is figuring out the language of first thirds of $S$. Let us denote this language by $L$. A good starting point is to consider the language $P$ of prefixes of $S$, since clearly $L \subseteq P$. The language $P$ is easy to find: it is
$$
a^ba^ba^ + a^ba^ + a^.
$$
With some work, you can show that $L$ and $P$ are rather close to each other, and so $L$ is regular. Details left to you.

More generally, if $S$ is any regular language, then the language $L$ of all first thirds of words in $S$ is always regular. The easiest proof of this is via NFAs. You can take it as a challenge, or look up material on the very similar operation of taking the first half of all words in a regular language.

Context

StackExchange Computer Science Q#97429, answer score: 4

Revisions (0)

No revisions yet.