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

### Finite State Machine that only accepts strings with number of 0's is less then number 1's [duplicate]

In case inf length of the strings (general case). In case we fix the maximum length. For example for strings with a size less than 12. Can you please suggest the diagram.
307 views

### Prove if $\{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$ is regular or not

$$L = \{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$$ To Prove: If given language is regular or not. I know that it is not a regular language but I am not able to come up with the string which I can ...
404 views

### Prove the language of numbers divisible by 3 is not regular using pumping lemma

I have a language $L$ that I think is not regular: $L = \{w\in \{0,1,...,9\}^* \; | \enspace w \enspace \text{is a decimal representation of a number divisible by 3}\}$ I'm using pumping lemma in my ...
68 views

### Is this language L regular?

Let's say we have the language L = {w $\in$ {a,b}$^*$ : ($\exists n \in \mathbb{N}$)[$w|_b = 5^n$]}. I want to know if this is a regular language or not. How do I go about doing this? I'm familiar ...
2k views

### Is the language of words containing equal number of 001 and 100 regular?

I was wondering when languages which contained the same number of instances of two substrings would be regular. I know that the language containing equal number of 1s and 0s is not regular, but is a ...
13 views

### Prove if {a^i b^j | i ≤ j} is a regular language or not [duplicate]

How can i prove if this language is regular or not? (i think is non regular)
16 views

16 views

### Regularity of language of words of prime length [duplicate]

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 ...
29 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 ...
774 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, ...
72 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?:)
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 ...