0
$\begingroup$

I have a problem with this following question:

Prove that the language $\{uw : |u|=2|w|\}$ is regular.

I tried to give this regular expression $(uw²)^*$ to resolve it.

$\endgroup$
  • 1
    $\begingroup$ As written, the language is not regular. Have you made a typo? Also, your proposed regex would accept uwwuwwuwwuww. $\endgroup$ – Ben I. Jun 6 '17 at 18:09
  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried towards proving your claim? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Jun 6 '17 at 18:40
  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jun 6 '17 at 18:40
  • $\begingroup$ @Smsarr The language definition leaves out that $u,w \in \Sigma^*$ for some alphabet $\Sigma$. $\endgroup$ – Raphael Jun 6 '17 at 19:12
2
$\begingroup$

Any string of the form $uw$ where $|u| = 2|w|$ is a string whose length is a multiple of $3$. We are therefore considering the language of strings over some alphabet $\Sigma = \{ a_1, \ldots, a_k \}$ (not specified in the question). whose length is a multiple of $3$. Let $\Sigma$ be the regular expression $a_1 + \cdots + a_k$. Then a regular expression descring the language in question is

$$(\Sigma\Sigma\Sigma)^*$$

$\endgroup$
  • $\begingroup$ Can we draw an automat modulo 3 $\endgroup$ – SARR Jun 6 '17 at 20:54
1
$\begingroup$

$r = (000 + 001 + 010 + 011 + 100 + 101 + 110 + 111)^*$

Update:

Proof: Without loss of generality assume that our alphabet is $\{0,1\}$. Then $uw$ consists of 0 and 1. Any string of 0 and 1s may by written as a concatenation of two strings $u$ and $w$. For example $010101110$ may be written as a concatenation of $u=010101$ and $w=110$. But the problem says that the length of $u$ must be two times of that of $w$, which has nothing to do with the symbols of $u$ and $w$. In other words the condition does not stipulate anything regarding the content of the strings. The string $uw$ may be any string of 0 and 1s providing it can be written as a concatenation of two strings $u$ and $w$ with length $|w|$ and $|u|=2|w|$. So, the string $uw$ has always length $|w| + 2|w| = 3|w|$, meaning that all strings in this language has lengths multiple of 3. Hence, any string of length 3k can be split up into $k$ substrings of length 3, that is one of $000, 001, 010, 011, 100, 101, 110,111$. QED


Example 1: $0101110 \notin L$ because its length is not multiple of 3.

Example 2: $010111000 \in L$ because its length is multiple of 3. We can take $w = 000$ and $u = 010111$.

$\endgroup$
  • $\begingroup$ $r =$ ... 0 to 7? $\endgroup$ – Ben I. Jun 6 '17 at 19:09
  • $\begingroup$ Raphael, proof added, Ben. I, they are simply all strings of length 3 of 0 and 1s. You would have 27 strings if you had 3 letter alphabet. $\endgroup$ – fade2black Jun 6 '17 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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