2
$\begingroup$

I have the following languages:

$ L_1 = (P \cup \{b\})^*$

$P = \{a^p | p = prime\}$ for example $ \{aa, aaa, aaaaa\} $

I am told that $L_1$ is regular and thus I should be able to create a finite automata for it, correct? But since $P$ cannot possibly be regular how can I draw this $union$ ?

This is what I have so far: (P | {b}) The $\{b\}$ part is fairly straight forward, but I am stuck on how to represent $P$

For example a valid string could be $\epsilon$, $bb$ or $aab$ but since I cannot keep track on how many a's we have gone trough so far how could I possible make a finite automata out of it? or would $aab$ be a invalid string and the regular expression of the whole thing would simply be $b^*$?

$\endgroup$
3
$\begingroup$

Given

$$L = (P \cup \{b\})^*, \quad P = \{a^p \mid p \text{ is prime}\}$$

you want to show that $L$ is regular.

Hint:

  • Set $P' = \{aa, aaa\} \subseteq P$ and observe that $L' = \big(\{aa, aaa, b\}\big)^* \subseteq L$.
  • Can you give a more direct definition of $L'$?

I hope this helps $\ddot\smile$

$\endgroup$
  • $\begingroup$ It helps but I am still confused :) Is however I try to draw a DFA for primes using combinations $a^2$ and $a^3$ (since every prime can be described with a combination of $2n+3m$) I can allways sneak in a non-prime to get to acceptance since I can allso easily describe $a^4$ the same way. $\endgroup$ – darrrrUC Sep 7 '16 at 14:05
  • $\begingroup$ @darrrrUC Ok, let me check one thing – please answer these two questions: does or does not $a^4 \in L'$, does or does not $a^4 \in L$? $\endgroup$ – dtldarek Sep 7 '16 at 14:22
  • $\begingroup$ $a^4$ is in neither, but could I not create it with a string such as $a^2$ $a^2$ Or is that just an invalid string since it adds to a $a^4$? Thank you for your patience :) $\endgroup$ – darrrrUC Sep 7 '16 at 14:38
  • $\begingroup$ What i ment is that $a^5$ is in $L$ and that is $a^2 + a^3$ ? $\endgroup$ – darrrrUC Sep 7 '16 at 14:39
  • $\begingroup$ @darrrrUC Check out the examples section: Kleene star. $\endgroup$ – dtldarek Sep 7 '16 at 15:59
2
$\begingroup$

Try first to figure what $P^*$ means - Some concatenation of words in prime length. Now note that for every $n \geq 2$ we can present him as $n = {p_1}^{a_1} \cdot ... \cdot {p_k}^{a_k}$ so for every $n \geq 2$ you can get that $a^n$ is in $P^*$.

Now we get that $L_1$ is actually every word that doesnt have lone $a$'s inside her - which is easy to identify using automata - whenever you get an $a$ that starts an $a$-sequence you going to a reject state, unless you get another $a$ right away.

$\endgroup$
  • $\begingroup$ In order to write $a^n$ as a concatenation of words of the form $a^p$ with $p$ prime, you need to express $n$ as a sum of primes, not a product. This is possible for $n \geq 2$ since then $n$ is a sum of $2$'s and possibly a $3$. $\endgroup$ – marlu Sep 7 '16 at 11:22
  • $\begingroup$ multiplication and power are actually a lot of additions, so it doesnt matter. However, I do agree that what you suggested would be more simple to understand. $\endgroup$ – Snufsan Sep 7 '16 at 11:24

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.