154 questions linked to/from How to prove that a language is not regular?
26 views

### Prove its not a regular language [duplicate]

I have a question. Assume $L = \{ a^m b^m \mid m ≥ 1 \}$ is not a regular language. Prove that $I = \{ a^{5n} b^{3m} c^n d^m \mid m,n ≥ 0 \}$ is not a regular language. I can prove it with pumping ...
106 views

### Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$ [duplicate]

I was trying to approach this proof, after multiple reads and attempts I am getting nowhere. If someone could help me out that would be great. Should I use the pumping lemma, if so how show I start, ...
57 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 [duplicate]

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

### Proving a language is Not Regular without using Pumping Lemma? [duplicate]

I was wondering how one would go about proving a language is Not Regular without using the traditional pumping lemma contradiction. $$L = \{ 1^k 0^n 1^n 0^k \mid k \geq 0, n \geq 0\}$$ I've seen a ...
57k views

115 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 :) ...
27 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 ...
75 views

### Prove that a language is not regular with process of elimination [duplicate]

When deterministic automaton, I need to prove that you can't implement the language in it, because the language is not regular. Easiest way to prove that a language is regular, is just by making an ...
120 views

### Is the language of words with equal number of 010s and 101s as substrings regular?

Is the language of words containing same number of 101s and 010s regular? If yes, how can I design a DFA for it? In general, is the language of words containing equal number of strings which one is "...
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.
163 views

### Pumping Lemma vs Myhill-Nerode [duplicate]

I was searching for a difference on both ways of proving that a language is not regular but I didn't came up with much. Let us take the following as an example: $$L = \{ a^n b^n \mid n \ge 0\}$$ ...
Hey was wondering if I'm applying the pumping lemma correctly for this proof or if this proof could be improved? Suppose $L = \{www:w\in\{0,1\}^*\}$ is a regular language. Let $p$ be the number from ...
### Provide “regular” grammar for this language {${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$} [duplicate]
I'm trying to understand the approach to constructing an grammar which accepts the language ${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$ } Thanks.