Questions tagged [regular-languages]

Questions about properties of the class of regular languages and individual languages.

Filter by
Sorted by
Tagged with
75
votes
10answers
103k views

How to prove that a language is not regular?

We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
47
votes
8answers
68k 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 ...
38
votes
0answers
1k views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
31
votes
5answers
5k views

Can regular languages be Turing complete?

I was reading about Iota and Jot and found this section confusing: Unlike Iota, where the syntactic tree for a string can branch either on the left or on the right, Jot syntax is uniformly left-...
31
votes
2answers
2k views

Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything ...
29
votes
2answers
1k views

Planar regular languages

In my class a student asked whether all finite automata could be drawn without crossing edges (it seems all my examples did). Of course the answer is negative, the obvious automaton for the language $\...
27
votes
1answer
876 views

Asymptotics of the number of words in a regular language of given length

For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that ...
24
votes
1answer
596 views

“Dense” regular expressions generate $\Sigma^*$?

Here's a conjecture for regular expressions: For regular expression $R$, let the length $|R|$ be the number of symbols in it, ignoring parentheses and operators. E.g. $|0 \cup 1| = |(0 \cup 1)^*| ...
23
votes
3answers
2k views

What are the conditions for a NFA for its equivalent DFA to be maximal in size?

We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in ...
19
votes
3answers
7k views

Pumping lemma for simple finite regular languages

Wikipedia has the following definition of the pumping lemma for regular langauges... Let $L$ be a regular language. Then there exists an integer $p$ ≥ 1 depending only on $L$ such that every ...
18
votes
3answers
334 views

Is this language defined using twin primes regular?

Let $\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$ Is $L$ regular? This question looked suspicious at the first glance and I've realized that it is connected with the ...
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
52k 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^{...
17
votes
1answer
281 views

Regular expressions with backreferences over unary alphabet

Setting: regular expressions with backreferences unary language (1-symbol alphabet) Is the following problem decidable in this setting: Given a regular expression with backreferences, does it ...
16
votes
3answers
6k views

Is there any uncountable Turing decidable language?

There are many(and I mean many) countable languages which are Turing-decidable. Can any uncountable language be Turing decidable?
16
votes
3answers
765 views

Number of words in the regular language $(00)^*$

According to Wikipedia, for any regular language $L$ there exist constants $\lambda_1,\ldots,\lambda_k$ and polynomials $p_1(x),\ldots,p_k(x)$ such that for every $n$ the number $s_L(n)$ of words of ...
16
votes
2answers
325 views

When is the concatenation of two regular languages unambiguous?

Given languages $A$ and $B$, let's say that their concatenation $AB$ is unambiguous if for all words $w \in AB$, there is exactly one decomposition $w = ab$ with $a \in A$ and $b \in B$, and ambiguous ...
16
votes
2answers
4k views

Are regular expressions $LR(k)$?

If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
16
votes
2answers
2k views

Decidablity of Languages of Grammars and Automata

Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2. Here are the two questions I'm looking at from a past exam. ...
15
votes
1answer
20k views

Intersection of context free with regular languages

The intersection of a context free language L with a regular language M, is said to be always context free. I understood the cross product construction proof, but I still don't get why it is context ...
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 ...
15
votes
1answer
555 views

The number of different regular languages

Given an alphabet $\Sigma = \{ a,b \}$, how many different regular languages are there that can be accepted by an $n$-state non-deterministic finite automaton? As an example, let us consider $n=3$. ...
15
votes
1answer
395 views

Exponential separation between NFAs and DFAs in the presence of unions

Recently an interesting question was asked and subsequently deleted. For a regular language $L$, its DFA complexity is the size of the minimal DFA accepting it, and its NFA complexity is the size of ...
14
votes
3answers
28k views

Infinite Language vs. finite language

I'm unclear about the use of the phrases "infinite" language or "finite" language in computer theory. I think the root of the trouble is that a language like $L=\{ab\}^*$ is infinite in the sense ...
14
votes
3answers
1k views

What are the possible sets of word lengths in a regular language?

Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$: $$\mathrm{LS}(L) = \{|u| \mid u \in L \}$$ Which sets of integers can be the length set of a regular language?...
14
votes
1answer
318 views

Is it decidable if a language described by number of occurences is regular?

It is known that the language of words containing equal number of 0 and 1 is not regular, while the language of words containing equal number of 001 and 100 is regular (see here). Given two words $...
14
votes
0answers
192 views

Using logic to prove non-regularity of a language

A language $L$ is regular if and only if it is definiable by a sentence in monadic second order logic (MSO) over strings (J.R. Buchi, Weak second-order arithmetic and Finite automata; Z. Math. Logik ...
13
votes
1answer
4k views

Is there a context free, non-regular language $L$, for which $L^*$ is regular?

I know that there are non-regular languages, so that $L^*$ is regular, but all examples I can find are context-sensitive but not context free. In case there are none how do you prove it?
13
votes
2answers
1k views

Closure against right quotient with a fixed language

I'd really love your help with the following: For any fixed $L_2$ I need to decide whether there is closure under the following operators: $A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\}$ $A_l(L)=\{...
13
votes
2answers
527 views

Is a unary language regular iff its exponent is a linear function?

While doing the current assignment for my formal languages and automata course, I kind of got stuck on exercises involving unary languages (I hope that's the right term), i.e., languages which build ...
13
votes
1answer
300 views

Finding maximal factorization of regular languages

Let language $\mathcal{L} \subseteq \Sigma^*$ be regular. A factorization of $\mathcal{L}$ is a maximal pair $(X,Y)$ of sets of words with $X \cdot Y \subseteq \mathcal{L}$ $X \neq \emptyset \neq Y$...
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
7answers
1k views

Is $A$ regular if $A^{2}$ is regular?

If $A^2$ is regular, does it follow that $A$ is regular? My attempt on a proof: Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A \cdot A$. Since concatenation of two non-...
12
votes
3answers
2k views

Regular languages that can't be expressed with only 2 regex operations

I thought all regular languages could be expressed with regular expressions (if a language is regular, it can be expressed with regex), but I have been told that you need all three of the regular ...
12
votes
4answers
12k views

Union of regular languages that is not regular

I've come across that question : "Give examples of two regular languages which their union doesn't output a regular language. " This is pretty shocking to me because I believe that regular languages ...
12
votes
3answers
2k views

Why are regular expressions defined with union, concatenation and star operations?

A regular expresssion is defined recursively as $a$ for some $a \in \Sigma$ is a regular expression, $\varepsilon$ is a regular expression, $\emptyset$ is a regular expression, $(R_1 \cup R_2)$ where ...
12
votes
3answers
2k views

Is there an efficient test for if an NFA accepts a subset of another NFA?

So, I know that testing if a regular language $R$ is a subset of regular language $S$ is decidable, since we can convert them both to DFAs, compute $R \cap \bar{S}$, and then test if this language is ...
12
votes
2answers
9k views

Intersection and union of a regular and a non-regular language

Let $L_1$ be regular, $L_1 \cap L_2$ regular, $L_2$ not regular. Show that $L_1 \cup L_2$ is not regular or give a counterexample. I tried this: Look at $L_1 \setminus (L_2 \cap L_1)$. This one is ...
12
votes
2answers
9k views

Are all context-free and regular languages efficiently decidable?

I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly $\mathrm{P}$). I perfectly understand that efficient problems are a ...
12
votes
2answers
2k views

How to prove regular languages are closed under left quotient?

$L$ is a regular language over the alphabet $\Sigma = \{a,b\}$. The left quotient of $L$ regarding $w \in \Sigma^*$ is the language $$w^{-1} L := \{v \mid wv \in L\}$$ How can I prove that $w^{-1}L$ ...
12
votes
2answers
2k views

If $L$ is a subset of $\{0\}^*$, then how can we show that $L^*$ is regular?

Say, $L \subseteq \{0\}^*$. Then how can we prove that $L^*$ is regular? If $L$ is regular, then of course $L^*$ is also regular. If $L$ is finite, then it is regular and again $L^*$ is regular. Also ...
12
votes
0answers
515 views

Test whether two languages are equal, when give in algebraic form

This sub-problem is motivated by Algorithm to test whether a language is regular. Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to ...
11
votes
5answers
2k views

A sufficient and necessary condition about regularity of a language

Which of the following statements is correct? sufficient and necessary conditions about regularity of a language exist but not discovered yet. There's no sufficient and necessary ...
11
votes
4answers
2k views

Star free language vs. regular language

I was wondering, since $a^*$ is itself a star-free language, is there a regular language that is not a star-free language? Could you give an example? (from wikipdia) Lawson defines star-free ...
11
votes
1answer
1k views

Algorithm to test whether a language is regular

Is there an algorithm/systematic procedure to test whether a language is regular? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n : n \in \mathbb{N}\...
11
votes
2answers
5k views

Single-tape Turing Machines with write-protected input recognize only Regular Languages

Here is the problem: Prove that single-tape Turing Machines that cannot write on the portion of the tape containing the input string recognize only regular languages. My idea is to prove that this ...
11
votes
1answer
211 views

Which non-regular languages are in $AC^0$?

For example, I know that the non-regular language $a^nb^n$ is in $AC^0$. I would like to know more examples like this.
11
votes
1answer
3k views

Prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties

I want to prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties. I understand pumping lemma can be used to prove that $\{0^n1^n \mid n \geq{} 0\}$ is not a ...
10
votes
3answers
2k views

Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)

The Problem There is no easy way to get a permutation with a regex. Permutation: Getting a word $$w=x_1…x_n$$ ("aabc") to another order, without changing number or kind of letters. Regex: Regular ...
10
votes
5answers
1k views

Language of the values of an affine function

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of the decimal expansions ...