Linked Questions

1
vote
1answer
131 views

Proving that language, with $|\Sigma|=1$, is irregular by Myhill–Nerode theorem

We have $\Sigma =\{0\}$ and $$L=\{0^{2^n} \mid n\ge 0\}$$ How to prove that $L$ is irregular by using Myhill–Nerode theorem? At other languages with $\Sigma >1$ we can usually separate the word or ...
2
votes
1answer
127 views

Is this the correct way to use the pumping lemma?

I've been watching lectures from Coderisland on YouTube about finite state machines, DFAs and NFAs, and in one discussion he talks about how to use the pumping lemma to show how a language is not ...
2
votes
2answers
138 views

Proving that $L = \{ a^{n!} \ | \ n \geq 0 \}$ is not regular

Let $L$ a language over $X = \{a\}$ defined as follow : $$L = \{ a^{n!} \ | \ n \geq 0 \}$$ I want to prove that $L$ isn't regular, I have searched in the forum for an equivalent question, but I ...
1
vote
0answers
155 views

Is the language of all DFAs that accept the empty language regular?

Is $E_{DFA}$ in the class of regular languages? $\qquad E_{DFA} = \{ \langle D \rangle \mid D \text{ is a DFA }, L(D) = \emptyset\}$ My argument is that it is because all of the DFAs in $E_{DFA}$ ...
1
vote
1answer
136 views

Proving $L = \{a^iba^j|i\ge2j\ge0\}$ isn't regular

I need to prove the following language is not regular, I think I need to use the pumping lemma. The trouble I am having is that there is multiple variables and I am not used to that. Could someone ...
1
vote
2answers
104 views

Proving that $a^{2^kp}$ isn't context-free (where $p$ goes over all primes)

I have this language and have to prove that its not context free: $$L = \{a^{2^kp } \mid k \in \mathbb{N}, p \text{ is prime number}\}.$$ Because it's unary, a context free language is also regular, ...
2
votes
1answer
103 views

How to choose a word to apply the Pumping Lemma?

I have some questions about the PUMPING LEMMA. First of all, I do not study computer science, I still go to school, but I'm very interested, so I could make mistakes. And sorry about my English :) ...
1
vote
1answer
60 views

How to show that the language made up of strings with nlogn 0s is not regular with the pumping lemma?

How to show that the following language is not regular with the pumping lemma? $$L=\left\{0^{n\lceil\log_2 n\rceil} \,\middle|\, n\in \mathbb{N}-\{0\}\right\}.$$
0
votes
1answer
57 views

DFA for $L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$

$L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$ Any idea? I have problem with this kind of task.
-1
votes
1answer
66 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?
0
votes
0answers
61 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$...
0
votes
0answers
58 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?
0
votes
1answer
47 views

The alphabet is {a, b}. Show that the set of words with the same number of occurrences of a and b is not regular

This is a question I've been asked to do and I honestly have no idea how to approach this. Help please?:)
0
votes
1answer
36 views

Create automata from non regular grammar

I have two grammars: L → ε | aLcLc L → ε | aLcLc | LL This two grammars are equals but the first one is regular, so it produces a regular language and a ...
0
votes
0answers
27 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?...

15 30 50 per page