# Linked Questions

149 questions linked to/from How to prove that a language is not regular?
5answers
60k 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....
8answers
67k 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 ...
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$....
4answers
51k views

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^{... 2answers 1k 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 ... 2answers 1k 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 1k 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 319 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 6k 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 762 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 ... 1answer 820 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 ... 4answers 731 views ### What is the number of expressions containing n pairs of matching brackets with nesting limit? I know the answer without nesting limit is the Catalan number. My question is, specifically, is there a recurrence relation that gives the number of expression containing$n\$ pairs of matching ...

15 30 50 per page