Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,761
questions
95
votes
10
answers
172k
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 ...
- 71.8k
53
votes
9
answers
122k
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 ...
- 879
42
votes
0
answers
2k
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})$? [closed]
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 ...
- 1,861
36
votes
5
answers
7k
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-...
- 567
36
votes
2
answers
2k
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 $\...
- 29.1k
32
votes
3
answers
13k
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 ...
- 883
32
votes
2
answers
3k
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 ...
- 883
31
votes
4
answers
100k
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^{...
- 313
29
votes
1
answer
1k
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 ...
- 274k
26
votes
1
answer
853
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)^*| ...
- 845
26
votes
3
answers
3k
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 ...
- 2,157
24
votes
7
answers
14k
views
Why is English not a regular language?
Surely any language with a finite longest word can be made regular by having an automaton with paths to 26 states for all letters and then having each of those states go to another 26 states, etc., ...
- 257
20
votes
3
answers
50k
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 ...
- 201
20
votes
1
answer
34k
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 ...
- 399
19
votes
3
answers
11k
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?
19
votes
3
answers
442
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 ...
- 2,157
19
votes
4
answers
8k
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$....
- 191
19
votes
1
answer
691
views
Exponential separation between NFAs and DFAs in the presence of unions
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 the minimal NFA accepting it. It is well-known that there is an ...
- 274k
19
votes
1
answer
377
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 ...
- 1,986
18
votes
5
answers
3k
views
Regular languages that seem irregular
I'm trying to find examples of languages that don't seem regular, but are. A reference to where such examples may be found is also appreciated.
So far I've found two. One is $L_1=\{a^ku\,\,|\,\,u\in \{...
- 403
17
votes
3
answers
999
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 ...
- 9,006
17
votes
3
answers
3k
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?...
17
votes
4
answers
3k
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 ...
- 271
16
votes
2
answers
447
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 ...
- 161
16
votes
2
answers
5k
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 ...
- 355
16
votes
2
answers
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. ...
- 1,115
15
votes
2
answers
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 ...
15
votes
2
answers
3k
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$ ...
- 879
15
votes
1
answer
940
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$. ...
- 1,861
15
votes
1
answer
8k
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 ...
- 345
15
votes
2
answers
449
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 $...
- 3,481
15
votes
0
answers
291
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 ...
- 12.4k
14
votes
2
answers
2k
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)=\{...
- 1,697
14
votes
2
answers
13k
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 ...
- 2,173
14
votes
0
answers
684
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 ...
D.W.♦
- 152k
13
votes
4
answers
4k
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 ...
- 249
13
votes
5
answers
3k
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 ...
- 2,173
13
votes
4
answers
3k
views
Proving Equivalence of Two Regular Expressions
Consider the regular expressions
$(1+01)^*(0+\epsilon)$
$(1^*011^*)^*(0+\epsilon) + 1^*(0+\epsilon)$,
where $\epsilon$ is the empty string. I need to determine if these expressions are equivalent. ...
- 257
13
votes
4
answers
3k
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 ...
- 981
13
votes
1
answer
7k
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?
- 583
13
votes
2
answers
1k
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 ...
- 315
13
votes
1
answer
367
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$...
- 534
12
votes
7
answers
2k
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-regular ...
- 321
12
votes
4
answers
20k
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 ...
- 279
12
votes
3
answers
3k
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 ...
- 383
12
votes
3
answers
3k
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 ...
- 29.5k
12
votes
3
answers
6k
views
Is Python a context-free language?
From Wikipedia: Off-side_rule#Implementation, there is a statement:
...This requires that the lexer hold state, namely the current
indentation level, and thus can detect changes in indentation ...
- 285
12
votes
2
answers
10k
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 ...
- 129
12
votes
2
answers
4k
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 ...
- 239
12
votes
1
answer
335
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.
- 313