Linked Questions

88
votes
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....
47
votes
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 ...
18
votes
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$....
17
votes
4answers
51k views

How to show that a “reversed” regular language is regular

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^{...
15
votes
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 ...
13
votes
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 ...
12
votes
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 ...
9
votes
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 ...
9
votes
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 ...
9
votes
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)\} $$ ...
8
votes
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 ...
8
votes
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 ...
7
votes
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 ...
7
votes
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 ...
6
votes
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