# Questions tagged [regular-languages]

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

77 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
190 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 ...
505 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 ...
431 views

### DFA, lower bound on number of states, language with primes and remainders

This is an exercise from old exam on formal languages that I don't know how to solve: Let $p \ge 5$ be a prime number and $L_p$ be a language of words over $\{0,1\}$ that read in binary from right (i....
209 views

### How to disambiguate symbolic regular expressions

What I mean by a "symbolic regular expression" (if there already is a different name for this I'm not aware of it) is a regular expression that may include exponents that are symbolic arithmetic ...
42 views

25 views

### Tree languages regular

Let $T_1,T_2 \subseteq T_\Sigma$ be regular tree languages, f a symbol with arity 2. To proof: $\{f(t_1,t_2) \mid t_1 \in T_1, t_2 \in T_2\} \subseteq T_{\Sigma \cup \{f\} }$ is regular. So it's ...
38 views

### Proving that the set of grammars generating L or L complement is undecidable

Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
47 views