Questions tagged [fl.formal-languages]

formal languages, grammars, automata theory

100 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
19 votes
0 answers
802 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 ...
Vince Vatter's user avatar
14 votes
1 answer
2k views

Is CFL strictly contained in NL?

We know that $\mathsf{REG}=\mathsf{NSPACE}(O(1))$ and $\mathsf{CSL}=\mathsf{NSPACE}(O(n))$. What is the relation of $\mathsf{CFL}$ and $\mathsf{NSPACE}(O(\log n))=\mathsf{NL}$? Is $\mathsf{CFL}$ a ...
cineel's user avatar
  • 241
13 votes
0 answers
216 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 ...
a3nm's user avatar
  • 9,269
13 votes
0 answers
181 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)$ ...
dtell's user avatar
  • 231
13 votes
0 answers
351 views

Survey on infinite alphabet automata?

The paper "Symbolic Finite State Transducers, Algorithms and Applications" by Bjorner et al (to appear at POPL 2012) describes one type of finite-state, infinite-alphabet automata/transducers by using ...
Huck Bennett's user avatar
  • 4,868
12 votes
0 answers
307 views

Reference request: exponential growth rates of subsequence-closed languages are integers

This question is migrated from MathOverflow, where it did not receive any answers a year ago. For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $...
Vince Vatter's user avatar
11 votes
0 answers
183 views

Are there cascade decompositions of machines that are more general than finite automata?

The idea of decomposing automata and their associated semi-groups into irreducible sub-components is due to Krohn & Rhodes and has been explored relatively thoroughly. Krohn & Rhodes gave an ...
Taylor Dohmen's user avatar
10 votes
0 answers
164 views

A language outside the Boolean closure of stochastic languages

Stochastic languages, that is, those accepted by probabilistic automata, are known to not be closed under intersection, union, concatenation, and morphism, even on unary languages. I have two ...
Michaël Cadilhac's user avatar
9 votes
0 answers
370 views

Deciding if a language induced by a Presburger formula is context-free

Is the following problem decidable? Given $n$ and a Presburger arithmetic formula $\phi(x_1,x_2,\dots,x_n)$, determine whether the language $\{a_1^{i_1} \dots a_n^{i_n}:\phi(i_1,i_2,\dots,i_n)\}$ ...
sdcvvc's user avatar
  • 1,291
8 votes
0 answers
207 views

Simplifying the disjoint union of wildcard strings

Setting: patterns with "don't care" symbols, binary alphabet. For example, pattern $x = 001?$ represents the set $L(x) = \{0010, 0011\}$. We are given a set $P$ of disjoint patterns: $L(x) \cap L(y) ...
Jukka Suomela's user avatar
8 votes
0 answers
1k views

Names for the left- and right-hand sides of a grammar production?

Problem I'm writing a document where I have to describe some of the properties of a type system as they relate to a particular formal grammar. I was trying to refer to the right-hand-sides of the ...
machine yearning's user avatar
8 votes
0 answers
1k views

Is there an ambiguity test for CFGs faster than trying all strings?

It is well known that testing whether a grammar is ambiguous is undecidable. It is however trivially decidable for any $G$ whether $L_n(G) := \{ w | w \in L(G) \wedge |w| \leq n \}$ for any $n \in \...
Alex ten Brink's user avatar
7 votes
0 answers
110 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, ...
Antimony's user avatar
  • 917
7 votes
0 answers
805 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 ...
Ulrik Rasmussen's user avatar
7 votes
0 answers
156 views

Has a result of Book and Greibach on Quasi-Realtime languages been improved?

Quasi-realtime languages are defined as languages accepted by nondeterministic multitape Turing machines in quasi-real time. Ronald Book and Sheila Greibach have shown in their 1970 paper that every ...
042's user avatar
  • 270
7 votes
0 answers
373 views

Examples of non-CSLs not created through diagonalization

Hopcroft & Ullman 1979, Intro to Automata Theory, Languages, & Computation states (p. 224) that "almost any language one can think of is CSL; the only known proofs that certain languages are ...
vzn's user avatar
  • 11k
7 votes
0 answers
344 views

The semantics of Parsing Expression Grammars

Is there a simple and intuitive explanation for the fact that the following parsing expression (where S is the starting symbol, $...
FloDo's user avatar
  • 81
6 votes
0 answers
72 views

Updating (minimal) DFA incrementally

Is there algorithm to incrementally update (minimal) DFA? Namely, having relatively large minimized DFA I want to update it incrementally using union and sudtraction with other (relatively small, ...
gsv's user avatar
  • 421
6 votes
0 answers
254 views

Context Free Grammar For Complement Of { wwwww | ... } With Minimal Locality?

Definitions Let $G$ be a context free grammar over an alphabet $\Sigma$ with non-terminals $V$. Define the locality $l(G)$ as the length of the longest word in $(V \cup \Sigma)^*$ that has a ...
Henning's user avatar
  • 59
6 votes
0 answers
232 views

Satisfiability and a Galois Theory Analog

Let $v(a, b)$ be a binary predicate, and define $\phi$ as follows: $$\phi: v(a_1, b_1) \land v(a_1, b_2) \land (a_1, b_3)$$ where our universe consists of two sorts $A: \{a_1, a_2, a_3\}$ and $B: \{...
Steven Schaefer's user avatar
6 votes
0 answers
99 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 ...
Kaban-5's user avatar
  • 245
6 votes
0 answers
285 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?...
a3nm's user avatar
  • 9,269
5 votes
0 answers
98 views

Useful notion of ambiguous growing context-sensitive language

As far as I understand there is no useful notion of ambiguous context-sensitive language. For example for any inherently ambiguous context-free language there is a context-sensitive grammar generating ...
naloa's user avatar
  • 61
5 votes
0 answers
163 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)$ ...
Andrey Lebedev's user avatar
5 votes
0 answers
163 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 (...
StefanH's user avatar
  • 2,077
5 votes
0 answers
157 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 ...
Joseph O'Rourke's user avatar
5 votes
0 answers
95 views

How much smaller can universal Turing machines get if they only need to be universal for a subclass?

Say that a Turing machine $U$ is universal for a class $\mathcal{C}$ of languages if for any language $L \in \mathcal{C}$, there is a word $w_L$ with: $$(\forall w)\quad w \in L \Leftrightarrow U(w_L, ...
Michaël Cadilhac's user avatar
5 votes
0 answers
169 views

The regularity of Markov chains with a threshold

(This question has been asked on math.se, with no response.) I am studying Paz's "Introduction to Probabilistic Automata" and there is an exercise I cannot solve: Ex. 11, p. 170: Let $\Sigma = \{a\...
Michaël Cadilhac's user avatar
5 votes
0 answers
247 views

Intersection between register automata and pushdown automata over infinite alphabet

I'm not an expert in automata theory, this is a reference request. As far as I have understood it is known in the automata comunity that register automata by Kaminski are closed by intersection with ...
Gianluca Mezzetti's user avatar
4 votes
0 answers
114 views

Learning a regular language with a specified closure property

Consider an alphabet $\Sigma$, and a partial transformation function $f:S\to\Sigma^\ast$ defined on some subset $S\subseteq\Sigma^\ast$. Let $S_f$ denote the set of strings $s\in S$ such that $f^n(s)\...
LegionMammal978's user avatar
4 votes
0 answers
77 views

Equivalent Characterizations of Semilinear Sets

Coming from an automata theory background, the semilinear sets seem like an ideal candidate for having lots of equivalent characterizations. I am already familiar with a few well known ones: Sets ...
TomKern's user avatar
  • 429
4 votes
0 answers
132 views

Languages recognized Counter DFA

I just randomly started fooling around with formal languages, grammars, and machines, and I have an extension to DFAs that I do not know what the class of languages it can recognize is. I'll give a ...
Adalynn's user avatar
  • 141
4 votes
0 answers
77 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 &...
Ville Salo's user avatar
4 votes
0 answers
268 views

Learning about Nested Stack Automata

I want to learn about nested stack automata. However my efforts to find a suitable learning resource have so far been abortive: The Wikipedia article on nested stack automata is a stub. Alfred Aho's ...
Aadit M Shah's user avatar
4 votes
0 answers
449 views

Is there a model theory for Haskell type classes?

I am trying to understand the semantics of Haskell’s type classes (TCs) from a model-theory point of view. It might difficult to give precise model theoretic semantics to type classes (see 1, and 2). ...
Pat's user avatar
  • 179
4 votes
0 answers
778 views

Variant of a proof using Ogden's lemma

I am trying to understand better the proof that the language $K=\{a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} is not context-free. (see It only looks like a homework problem…), and the use of ...
babou's user avatar
  • 1,542
4 votes
0 answers
575 views

Minimal context-free Grammar for a special one-letter Language

For natural numbers $n \geq 5$, $m \geq 2^{n-2} + 1$ the following context-free language is given: $$ L_{n,m} = \{ a^i | 2 \leq i \leq m \} \setminus \{a^{2^i}|2 \leq i \leq n-2\} $$ Find and ...
Ronny's user avatar
  • 301
4 votes
0 answers
319 views

Is $\{a^n b^m : 1 \le m \le 2^{2^n}\}$ a permitting-context language?

A random permitting-context grammar is a context-free grammar $(N, \Sigma, P, S)$ equipped with a function $p : P \rightarrow 2^N$. The rule $A \rightarrow x$ can be applied to $uAw \Rightarrow uxw$ ...
Max's user avatar
  • 1,561
3 votes
0 answers
32 views

Modify DCFG to enforce length limit

Given a deterministic context-free grammar $G$ that generates the language $L$, is there an efficient algorithm that can be used to construct another DCFG $G_N$ that generates the language $\{ s \in L ...
Jerry Ding's user avatar
3 votes
0 answers
110 views

Proof: Why are MM-1QFA strictly more powerful than MO-1QFA? (Quantum automata)

While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97). More ...
catalyst's user avatar
3 votes
0 answers
111 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,...
Blanco's user avatar
  • 421
3 votes
0 answers
47 views

Extending the sequential calculus (logic over words) to allow a hierarchy of languages like the arithmetical hierarchy

Let $\Sigma$ be some finite alphabet. Then consider the logical language $\mathcal L = \{ R_a : a \in \Sigma \} \cup \{ <,= \}$ and first order formulas. For a given first order formula $\varphi$ a ...
StefanH's user avatar
  • 2,077
3 votes
0 answers
127 views

Justifying the state of virtual memory as a vector space

First, I'm mostly experienced with Math, which I hope won't be too inconvenient. I saw Operational Calculus on Programming Spaces by Sajovic and Vuk, which seemed very interesting to me (for a "short ...
Mark Schultz-Wu's user avatar
3 votes
0 answers
96 views

Grammar with "dead" derivation chains

This question is inspired by the great answer given by Jeffrey Shallit on my question about proper CSG for $a^n b^n c^n$ language. Disclaimer:: I'm not arguing about correctness of this grammar. This ...
Andrey Lebedev's user avatar
3 votes
0 answers
175 views

Context-Sensitive Grammar characteristic properties

This question can look like some kind of puzzle, but it is actually part of more complex applied problem. Let's consider subspace of Context-Sensitive Grammars, which contains grammars which can not ...
Andrey Lebedev's user avatar
3 votes
0 answers
103 views

A question on the introduction of the Wagner hierarchy from K. Wagner's original paper

My question is related to the seminal paper On $\omega$-regular sets by K. Wagner, which introduced a hierarchy which is now know as the Wagner- (or Wadge-) hierarchy of $\omega$-regular sets. In ...
StefanH's user avatar
  • 2,077
3 votes
0 answers
207 views

Mildly dependently-typed metalanguage for mildly context-sensitive object languages

This is almost certainly not a new idea, but I haven't seen it elaborated or discussed elsewhere. A very natural way to represent the abstract syntax of an object language in a typeful metalanguage is ...
isekaijin's user avatar
  • 501
3 votes
0 answers
160 views

Is there research on "minimal" Turing-universal Markov algorithms?

The Markov algorithm is a simple model of computation. For other models of computation, such as Turing machines, cellular automata, tag systems, etc., there is research on the "minimal" instances of ...
N. Virgo's user avatar
  • 699
3 votes
0 answers
149 views

Restricted-Input Automaton

In the classic setting, an automaton for a language $L$ is required to accept all words in $L$ and reject/get stuck on every word in $\Sigma^*\setminus L$. All of the related concepts are then ...
R B's user avatar
  • 9,448
3 votes
0 answers
176 views

Deciding whether a binary multiplicity automaton has empty language

Multiplicity automatons (see here) is an interesting model. They have the (almost) same syntax as a non-deterministic finite automatons, but instead of deciding whether a word belongs to a language, ...
R B's user avatar
  • 9,448