Questions tagged [regular-languages]

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

1,199 questions
Filter by
Sorted by
Tagged with
106k 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 ...
71k 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 ...
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 ...
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-...
2k views

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 ...
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 ...
54k views

194 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 ...
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?
1k views

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.
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 ...
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 ...
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 ...