149 questions linked to/from How to prove that a language is not regular?
26 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 ...
90 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 "...
56 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.
76 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\}$$ ...
74 views

### Show that the language L = {www : w ∈ {0, 1} ∗} is not regular [duplicate]

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 ...
47 views

### Why is this not recognized by a DFA?

I am still confused over my professor's explanation on why this problem is not a DFA. The Problem: Explain why $L = \{p^kq^k \mid k>0\}$ cannot be recognized by a DFA My professor explained it as ...
52 views

### 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.
84 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 :) ...
53 views

### If there is comparison between two variables then language is not regular. Then how the below two languages L1 and L2 Regular? Please Explain [duplicate]

How these two languages be regular.If there is comparison between m and n since (n < m) is the condition to be satisfied.
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\}.$$
55 views

### Proving a language is non-regular using the Pumping Lemma for non-binary strings [duplicate]

I am unsure of how to prove this language is non-regular. I do not even know where to start to develop a string that would prove the language is non-regular by contradiction. Any help would be ...
17 views

### Regular grammar question [duplicate]

Define a regular expression such that there is a string of 1 or more a's continuous followed by a continuous string of b's so that the number of a's and b's are the same. I have ideas on how i would ...
35 views

### Proving that language is regular or not [duplicate]

How to prove that the language over the alphabet $\{0, 1, +, =\}$ is regular or not: $\{a+b=c:a,b,c \text{ are integers in binary for which } a \text{ plus } b\text{ equals } c\}$ I started with the ...