156 questions linked to/from How to prove that a language is not regular?
69k views

### How to prove that a language is not context-free?

We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free....
80k views

### How to prove a language is regular?

There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular? For instance, if I am given that $L$ is regular, how can I prove that ...
I'm stuck on the following question: "Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{... 4answers 7k views ### Using Pumping Lemma to prove language$L = \{(01)^m 2^m \mid m \ge0\}$is not regular I'm trying to use pumping lemma to prove that$L = \{(01)^m 2^m \mid m \ge0\}$is not regular. This is what I have so far: Assume$L$is regular and let$p$be the pumping length, so$w = (01)^p 2^p$.... 2answers 2k views ### Number of words of a given length in a regular language Is there an algebraic characterization of the number of words of a given length in a regular language? Wikipedia states a result somewhat imprecisely: For any regular language$L$there exist ... 4answers 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 ... 2answers 2k views ### Does the language of Regular Expressions need a push down automata to parse it? I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular ... 3answers 2k views ### How to feel intuitively that a language is regular Given a language$ L= \{a^n b^n c^n\}$, how can I say directly, without looking at production rules, that this language is not regular? I could use pumping lemma but some guys are saying just looking ... 3answers 2k views ### Is$(a^nb^m)^r$regular? I took my theory of computation exams a few weeks ago, and this was one of the questions: Assume language$L=\{(a^nb^m)^r \mid n,m,r\ge 0\}$Is L regular? If yes provide a regular expression ... 2answers 346 views ### Regularity of unary languages with word lengths the sum of two resp. three squares I think about unary languages$L_k$, where$L_k$is set of all words which length is the sum of$k$squares. Formally: $$L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\}$$ ... 2answers 1k views ### Proof of non-regularity, based on the Kolmogorov complexity In class our professor showed us 3 methods for proving non-regularity: Myhill–Nerode theorem Pumping Lemma for regular languages Proof of non-regularity, based on the Kolmogorov complexity Now the ... 1answer 7k views ### Proof that$a^{n^2}$is not regular Show that$L=\{a^{n^2} | n \geq 0\}$is not regular Hey guys. I'm taking a CS class and this stuff is really new to me so bear with me. I tried to look if I get some contradiction by using the ... 1answer 1k views ### What's wrong with my pumping lemma proof? The language$L = \{0^{2n} \space |\space n \ge 0 \}$is obviously regular – for example, it matches the regular expression$(00)^*$. But the following pumping lemma argument seems to show it's ... 1answer 858 views ### Is the language of binary representation of perfect squares regular? Let$\mbox{bin}(n)$denote the binary representation of an integer$n$. Let$L = \{ \mbox{bin}(n^2) \mid n \in \mathbb{N} \}$. Is$L$a regular language? I think one can prove that$L\$ is not ...
I am practising problems on Regular Languages and I came across this question: Prove that the language $$\{a^m b^n : m ≥ 0, n ≥ 0, m \ne n\}$$ is not regular. (Using the pumping lemma for this ...