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

Is there a context free, non-regular language $L$, for which $L^*$ is regular?

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

Problem

I know that there are non-regular languages, so that $L^*$ is regular, but all examples I can find are context-sensitive but not context free.

In case there are none how do you prove it?

Solution

$L = \{a^n b^n \mid n\in\mathbb{N}\}$ is context-free but not regular (classical example). So is $L' = \{a^n b^n \mid n\in\mathbb{N}\} \cup \{a,b\}$.

$L'^\ast = \{a,b\}^\ast$ is regular.

Context

StackExchange Computer Science Q#2081, answer score: 21

Revisions (0)

No revisions yet.