# Questions tagged [fl.formal-languages]

formal languages, grammars, automata theory

378 questions
Filter by
Sorted by
Tagged with
28 views

68 views

### Relation between REG and NLOGTIME?

What is known about the relation between the class of regular lanuages and NLOGTIME? Is any class contained in another one? You have some choice of how to define NLOGTIME to get one or both ...
96 views

### Possibly small circuit complexity class containing REG?

What is the smallest well-known Boolean-circuit complexity class containing all the regular languages over the binary alphabet {0,1}? If we believe Theorem 2 in Koucký, Circuit Complexity of ...
267 views

### Converting Kuroda normal form rules to the Penttonen normal form

Let us say we have some abstract context-sensitive grammar in the Kuroda normal form, which is where all production rules are of the form: $AB\rightarrow CD$ or $A\rightarrow BC$ or $A\rightarrow B$...
376 views

### What is the complexity of counting parse trees?

A Counting Problem Given a CFG $G$ and a string $s$, how many distinct parse trees are there for the string $s$? An Example Instance Let's consider an example instance consisting of a CFG $G$ with ...
293 views

### Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$?

$CFL$ is the class of context-free languages. Question Is $CFL$ known to be solvable in $o(log^{2}(n))$ non-deterministic space? What about $DCFL$?
118 views

### Deterministic context-free languages that can be represented as the word problem of a group

Consider a group $G$. We call $G$ virtually free is it contains a free subgroup of finite index. If $G$ is finitely generated by some set $X \subseteq G$ one can consider the word problem $WP(G)$ ...
71 views

### Looking for a particular normal form for Context-sensitive grammar

I am wondering if there is a described normal form for Context-sensitive grammar, which is something similar to Kuroda normal form and Greibach normal form. That is to say, each rule in such form ...