Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

$L_1=\{a^ku \mid u \in \{a,b\}^* $ and $u$ contains at least $k$ a's, for $k\geq 1\}$.

If it is regular, I haven't found its regular expression or any closure property to prove it.

If not, it seems pumping theorem holds for it...

Also, what about the language where the above "at least" is changed to "at most"?

share|improve this question
add comment

2 Answers

Take $k=1$. No need to go further, any more $a$ can be absorbed by $u$ without risk.

So you need $u$ to have at least 1 $a$ and only $a$'s or $b$'s. Therefore, $L_1$ is described by $a(a|b)^*a(a|b)^*$ and is regular.

For the side question (at most $k$ $a$'s, let's call that language $L_2$), you can reason in a similar fashion to get $u$ as small as possible. For simplicity let's consider $L_3$ the intersection of $L_2$ with the one denoted by $a^*ba^*$. You have $L_3=\{a^k b a^j, k \geq j\}$. Intersection with its reverse yields $\{a^kba^k\}$ which is not regular, therefore $L_2$ is not regular either since regular languages are closed under intersection and reversal.

share|improve this answer
    
No, because $aaaabaaaa$ should be accepted whereas $aaaabaaa$ should not. –  Pål GD Jan 17 '13 at 16:20
2  
@PålGD $aaaabaaa=au$, with $u=aaabaaa\in\{a,b\}^*$. $6>=1$. Please point out why it shouldn't be accepted. –  Khaur Jan 17 '13 at 16:21
    
Because I'm a moron. You are absolutely correct. It is regular. –  Pål GD Jan 17 '13 at 16:29
    
Thanks. I have deleted my (wrong) answer. –  Hendrik Jan Jan 17 '13 at 16:40
    
Nice. You are tempted to think of it in terms of $u = bu'$, which is a completely different story. –  Raphael Jan 17 '13 at 16:59
show 3 more comments

They way I read the question for the first time, I understood $k$ to be a fixed parameter. Define the following languages, for $k\ge 1$:

$$L_k = \{ a^ku \mid u\in \{a,b\}^* \text{ and $u$ has at least $k$ $a$'s }\}$$

$$\tilde L_k = \{ a^ku \mid u\in \{a,b\}^* \text{ and $u$ has at most $k$ $a$'s }\}$$

The difference is that for any $L_k$, $k$ is only one specific fixed value (while one can understand $L_1$ to be the union for any $k\ge1$).

Still, those languages are regular. A regular expression for the first might be $a^kb^*\underbrace{ab^*\ldots ab^*}_{k \text{ times}}(a+ b)^*$. A regular expression for the second may be $a^kb^*\Big(a+ab^*a + ab^*ab^*a + \ldots + \underbrace{ab^*ab^*\ldots a}_{k-1\ a\text{'s}}\Big)b^*$. It is not too hard to come up with NFAs for both languages.


This gives a very nice example about (infinite) unions of regular languages: although $L_k, \tilde L_k$ are regular for any $k$, and although regular languages are closed for unions, when we take their infinte unions (abusing notations!): $$ L_1 = \bigcup_k L_k \qquad L_2 = \bigcup_k \tilde L_k$$ $L_1$ is regular, while $L_2$ is not!
(where $L_1$ is defined in the OP's question, and $L_2$ is the like $L_1$ but with "at most")

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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