Questions tagged [fl.formal-languages]
formal languages, grammars, automata theory
100
questions with no upvoted or accepted answers
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 ...
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 ...
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 ...
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)$ ...
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 ...
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 $...
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 ...
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 ...
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)\}$ ...
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) ...
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 ...
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 \...
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, ...
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 ...
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 ...
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 ...
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, $...
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, ...
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 ...
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: \{...
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 ...
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?...
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 ...
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)$ ...
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 (...
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 ...
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, ...
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\...
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 ...
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)\...
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 ...
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 ...
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 &...
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 ...
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). ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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,...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...