# Questions tagged [fl.formal-languages]

formal languages, grammars, automata theory

88 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
645 views

### Why is the Pumping Lemma sometimes called Bar-Hillel's Lemma?

There are several papers in the literature that refer to the Pumping Lemma for context free languages as Bar-Hillel's Lemma (for example, here, here, and on the Wikipedia page). However, the first ...
2k views

### minimizing size of regular expression

Suppose we have a regular language specified by a regex, for example, (ab|ac)* and we wish to find an equivalent regex with the minimal number of symbols, (a(b|c))*. Is there any efficient way to do ...
371 views

### Can we approximate the number of words accepted by an NFA?

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete. The second ...
170 views

### Regular languages accepted by an automaton with at most one transition per letter

I'm interested in the (very restricted) subset of regular languages for which there is an automaton having the following property: for every letter $a$ of the alphabet, the automaton has at most one ...
157 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 $W\!P(G)$ ...
289 views

1k views

85 views

### Reference request: transforming a grammar to Greibach normal form preserves the number of parse trees

I believe that most "natural" ways of transforming a grammar to the GNF should preserve the number of parse trees for each string. For example, Urbanek's construction from the paper "On Greibach ...
633 views

### Does PEG contain CFG?

Despite their considerable expressive power, all PEGs can be parsed in linear time using a tabular or memoizing parser (8). These properties strongly suggest that CFGs and PEGs define incomparable ...
276 views

### Language of stack configurations of a pushdown automaton

Consider a pushdown automaton $A$ with stack alphabet $\Gamma$. Let $L$ be the language on $\Gamma$ of the stack configurations encountered during accepting runs of $A$. Is $L$ a context-free language?...
161 views

### “Context” understanding in tree grammars

The Context-Free tree grammar has rules of the form: $A\rightarrow t$ or $A(x_1,\dots,x_n)\rightarrow t_x$, where $A\in N$, $t\in T(N\cup T)$, $t_x\in T(N\cup T\cup \{x_1,\dots,x_n\})$, $T(Z)$ ...
107 views

### Salomaa's axiomatisation of regular languages and the use of regular expression in it

I am reading the classical article of A. Salomaa where he gives two axiom systems for regular sets and proofs consistency and completeness. As I have understood it, an axiomatic system in some logic (...
150 views

### Mastery-based grading for Theory of Computation

I would be interested to learn of anyone's experience using mastery-based (or "mastery-level") grading in a Theory of Computation course. Usually this requires—at a minimum— a detailed ...
77 views

62 views

### Necessary and sufficient condition for an infinite tree to be context-free

A Buchi automaton is non-empty iff it accepts an infinite word of the form $uv^\omega$ (here $u,v$ are finite words). In other words, if $\{w\}$ is an $\omega$-regular language, then it is of that ...