157 questions linked to/from How to prove that a language is not regular?
68 views

### Use the pumping lemma to show that the language is not regular [closed]

I am working on this problem : Use the pumping lemma to show that the language $\{0^n 1^{n} \mid n ≥ 1\}$ is not regular. May someone give me some suggestion about how to solve this problem?
62 views

### How to prove that the language of words ucv with as many a's in u as b's in v is irregular?

I'm trying to prove that: $L=\{w\in\{a,b,c\}^*\Big|\#_a(u)=\#_b(v),\ \ w=ucv,\ \ \ u,v\in\{a,b\}^*\}$ is irregular, so I'm trying to use the Pumping Lemma. This is what I tried so far: $w=a^ncb^n$...
60 views

### proving L = {$a^{100}yy^r : \forall y \in$ {a,b}*} is not regular

I need to prove that L = {$a^{100}yy^r : \forall y \in$ {a,b}*} is not regular. i have tried using pumping lemma but couldn't get far with it. Any help in where i should go with it?
34 views

### Using Nerode theorem to prove that the following languages are non-regular

I've been trying to understand the idea behind proving a language is not regular by using Nerode's theorem, but I just couldn't apply the idea on what I've been asked. The problem is to prove the ...
31 views

### Language of strings of lengths that are prime is regular? Is C^* regular? [duplicate]

With $\Sigma = \{a\}$ I want to see if a language $C = \{a^p \ | \ p \ \text{is prime}\}$ is regular and whether or not $C^*$ is regular. How would I go about showing whether $C$ or $C^*$ are regular?...
25 views

### Pumping lemma for non regular languages [duplicate]

I read that pumping lemma is sufficient condition to prove non regularity of languages but not necessary condition. I know the first part that it is sufficient is true but not able to understand why ...
Is the following language regular? $$L_{\mathit{prime}} = \{ w \in \{0,1\}^* : |w| \text{ is prime} \}.$$ I have to either provide a DFA (if the language is regular), or prove that it is not ...