# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

274 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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})$?

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,841
271 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.2k
651 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 ...
• 141k
310 views

### Is unary language with polynomial power context sensitive?

I suppose that $\Sigma = \{a\}$. Prove or Disprove: For every polynomial $p(n)$ with coefficients in $\mathbb{N}$, $L = \{a^{p(n)} \; | \; n \in \mathbb{N}\}$ is a context sensitive language. It ...
• 151
319 views

### Is there a strictly non-deterministic one-counter language whose complement is one-counter?

Let $A= \{L \mid L \;\text{is one-counter and $$\bar{L}$$ is also one-counter} \}$ Clearly, $\text{Deterministic one-counter} \subseteq A$ Is it the case that $A = \text{Deterministic one-counter}$...
• 1,239
567 views

• 665