# Questions tagged [fl.formal-languages]

formal languages, grammars, automata theory

401 questions
Filter by
Sorted by
Tagged with
0answers
13 views

### Intuition on context free and other kinds of a forests? Data structures perspective

I am trying to gain intuition on formal forests, also called tree languages, i.e., sets of trees. There are regular tree languages, and there are context free tree languages. They both come in a ...
1answer
130 views

### Ambiguity of regular expressions

Some regular expressions are ambiguous. Some are not. a*b* is unambiguous for example. Expression a*a* is ambiguous but it can ...
1answer
74 views

### Conditioning Probability on a Language With Measure 0

Let $\Sigma = \{ 1, 2, \ldots, n\}$ be some alphabet. Assume that you have a coin with n-sides (each side corresponds to a letter in $\Sigma$), and we get each letter with equal probability. Now you ...
1answer
119 views

### Different definitions of grammar complexity

It's known that there are different "kinds" of grammar complexity of language $L$ --- nonterminal complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L$), covering ...
0answers
65 views

### Terminology for languages of pairs of words

I want to consider $L \subset A^* \times B^*$ as a "language". Is there standard terminology for this? I wrote "double language" first (but that doesn't sound right to me), then &...
0answers
59 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 ...
1answer
244 views

### Can we efficiently convert from NFA to smallest equivalent DFA?

Definitions For any automaton $X$, let $L(X)$ denote the language recognized by $X$. For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$. ...
1answer
64 views

### Definition of Rabin acceptance condition for omega automatons [closed]

I've been trying hard to understand something. According to wikipedia and this paper, the definition of the Rabin acceptance condition involves a set of pairs of states. I've been told that the left ...
1answer
157 views

### Languages whose Parikh image is recognizable

Let $\Sigma$ be some alphabet, and $p : \Sigma^* \to \mathbb N_0^{|\Sigma|}$ the Parikh map. A formal language $L \subseteq \Sigma^*$ is called a slip-language, if $p(L)$ is a semilinear set. By ...
1answer
50 views

### Reduction of a language to a shorter equivalent [closed]

I'm new to Theoretical Computer Science, and my textbook says that it is easy to verify that the following language \begin{array}{l} L_{1}=A^{*} \cdot\{b\}-\left(A^{*} \cdot(A-\{a\}) \cdot A^{*} \cdot\...
2answers
493 views

### Reversible Turing tarpits?

This question is about whether there are there any known reversible Turing tarpits, where "reversible" means in the sense of Axelsen and Glück, and "tarpit" is a much more informal concept (and might ...
3answers
2k views

### What are graph grammars?

I have found information on graph grammars and graph rewriting, but the papers that I find on it are a bit thick. Can someone give a quick overview of what graph grammars are, as well as an overview ...
1answer
86 views

### Nonterminal descriptional complexity of regular languages

Recently I became interested in grammar complexity of regular language. Prior to searching for literature, I tried to investigate it on my own, proving two lemmas from comment below. I am aware of an ...
0answers
97 views

### Deciding whether DCFG is visibly pushdown

Is the following problem decidable? If so, what's the best algorithm known? Instance: a deterministic pushdown automaton $A$ Question: Does there exist (i) some partition of the alphabet into push, ...
1answer
122 views

### how to define “correlation” between languages?

How does one define the concept of correlation between languages? Is there any 'standard' measure of 'correlation' between two (possibly inf) sets of strings / an analogue of the concept in this ...
5answers
3k views

### Recovering a parse forest from an Earley parser?

I was recently reading up on the Earley parser and think it's one of the most elegant algorithms I've seen to date. However, the algorithm in its traditional sense is a recognizer and not a parser, ...
2answers
831 views

### Büchi automata with acceptance strategy

The problem Let $A=\langle \Sigma, Q, q_0,F,\Delta\rangle$ be a Büchi automaton, recognizing a language $L\subseteq\Sigma^\omega$. We assume that $A$ has an acceptance strategy in the following sense :...
0answers
168 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 ...
1answer
100 views

### Generalizations of Dyck languages?

The "narrowest" generalization of Dyck languages that I am aware of is Visibly Pushdown languages. Are there any useful classes of languages that are intermediate between Dyck languages and ...
5answers
4k views

### Counting words accepted by a regular grammar

Given a regular language (NFA, DFA, grammar, or regex), how can the number of accepting words in a given language be counted? Both "with exactly n letters" and "with at most n letters" are of ...
1answer
138 views

### What graphs on $\mathbb{N}$ can be encoded as regular languages?

Suppose I represent the natural number 0 by "x", and use the symbol "s" for successor so that I get the following encoding of $\alpha : \mathbb{N} \rightarrow V$ of natural numbers ...
0answers
23 views

### Decidability of regular partition construction given its existence

Let $G = (N,T,P,S)$ be a context-free grammar where $T,N$ are sets of terminals and nonterminals respectively, $P$ contains all the productions of the grammar, and $S \in N$. If we know that $G$ is LL(...
0answers
15 views

### Power of Hyperedge Replacement Grammars (HRGs)

Can HRGs generate languages which equal or include the following graph languages: All (bipartite) graphs of bounded degree All (bipartite) planar graphs of bounded degree All (bipartite) planar ...
0answers
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 ...
2answers
3k views

### computing the minimal NFA for a DFA

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known ...
8answers
6k views

### What are the simplest turing-complete systems? [closed]

Lambda Calculus is very simple. Are there even simpler turing-complete systems? Which is the simplest of them all?
3answers
294 views

### Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?

As an undergraduate with limited understanding of QC and even the C-T thesis, I have problems figuring out why in questions such as Extended Church-Turing Thesis real-life quantum stuff is even given ...
1answer
126 views

2answers
476 views

### Does a given regular language contain an infinite prefix-free subset?

A set of words over a finite alphabet is prefix-free if there are no two distinct words where one is a prefix of the other. The question is: What is the complexity of checking whether a regular ...
4answers
2k views

### Proving the set of powers of 2 over ternary alphabet to be non regular.

It's simple to see that the powers of 2 over alphabet {0,1} is regular because $10^*$ is a regular expression for it. But the powers of 2 represented in ternary appears to be non regular. Pumping ...
3answers
424 views

### Is the complement of { www | … } context-free?

It is well-known that the complement of $\{ ww \mid w\in \Sigma^*\}$ is context-free. But what about the complement of $\{ www \mid w\in \Sigma^*\}$?
0answers
89 views

### The number of words of length $n$ in a context-sensitive language

Let $L$ be a context-sensitive language, $s_{L}(n)$ is denoted by the number of words of length $n$ in $L$. What is known about $s_{L}(n)$? Note that it is known that $s_{L}(n)$ is either polynomial,...
1answer
102 views

### Term for a set that is not immune

At the outer bounds of computational complexity classes are those defined through computability theory (AKA recursion theory). This is where we get the well known complexity classes such as R, RE, and ...
2answers
170 views

### Is the decidability of a language decidable? [closed]

Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language? Comments + answer say trivially the answer is yes; however, I'm wondering here would ...
3answers
374 views

### what is a model of computation, mathematically? [closed]

Where can I find a mathematical definition for "model of computation"? https://en.m.wikipedia.org/wiki/Model_of_computation doesn't provide a precise definition for "model of computation"--it doesn't ...