formal languages, grammars, automata theory

learn more… | top users | synonyms (2)

1
vote
1answer
64 views

Deterministic Parity Automata require unbounded index

Deterministic parity automata $(Q, \Sigma, q_0, \Delta, c)$ are powerful enough to recognize all $\omega$-regular languages. However, the number of priorities they require for a language can become ...
4
votes
0answers
55 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, ...
2
votes
2answers
75 views

If the set of factors of an infinite word $\xi$ is regular, is this property stable under “shift's” of $\xi$?

Let $\xi$ be an infinite binary sequence, and denote by $T(\xi)$ the set of all factors (infixes) of $\xi$. Also if $w$ is some finite prefix of $\xi$, denote by $\xi/w$ the unique $\eta$ such that $w ...
-1
votes
0answers
28 views

How to formally describe the following type?

I want to describe a type $T$ formally, using mathematical notion such as sequence, set or something else. An example of element of such type $T$ is Every element in such type $T$ satisfying the ...
8
votes
1answer
187 views

What is the state complexity of the copy language?

Let a number $n$ be given. Consider the following language $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$. In words, $L_n$ is the set of copy strings of length $2n$. Consider the following ...
17
votes
1answer
315 views

“Embedding” a language in itself

Main/General Question Let $L$ be a language. Define the languages $L_i$ with $L_0 = L$ and $$L_i = \{xwy : xy \in L_{i-1}, w \in L\}$$ for $i \geq 1$. Consider $\hat{L} = \bigcup L_i$. So, we ...
4
votes
1answer
65 views

Is there any research or findings on creating parse forests on Earley parsers with Leo Joop Enhancements?

Using the Earley Algorithm we can use the Leo enhancement to create cached items for recognition. http://www.sciencedirect.com/science/article/pii/030439759190180A Scott's algorithm on building ...
8
votes
2answers
114 views

Separating lists of words

There is an open problem in formal languages known as the Separating Problem; which is briefly stated as given two distinct strings of length $n$, how large of a DFA is required to "separate" them, ...
1
vote
0answers
170 views

Complexity of DBA-recognizable Omega-Languages

Given an $\omega$-regular expression $r$, how difficult is it to decide if $L(r)$ is recognizable by some deterministic Büchi automaton? I know it is solvable in EXPTIME by converting the regular ...
3
votes
2answers
105 views

Translation of context-free parsing into SAT

Is there a published algorithm for translating a context-free parsing problem into SAT? That is, an algorithm that translates a context-free grammar and an input string into a set clauses that is ...
11
votes
2answers
199 views

Vector Addition Systems with finite “obstacles”

A Vector Addition System (VAS) is a finite set of actions $A \subset \mathbb{Z}^d$. $\mathbb{N}^d$ is the set of markings. A run is a non-empty word of markings $m_0 m_1\dots m_n$ s.t. $\forall i \in ...
9
votes
2answers
127 views

Minimizing Automata accepting $\omega$-words (i.e. infinite words)

What is the standard approach on minimizing Büchi-Automata (or also Müller-Automata)? Transfering the usual technique from finite words, i.e. setting two states to be equal if the words "running out" ...
7
votes
1answer
96 views

Extensional characterization of non-deterministic finite state transductions

I recently became aware of the rather appealing characterization of deterministic word-to-word transductions as word functions with bounded variation (see e.g. [1]). This coincides with the set of ...
5
votes
1answer
169 views

Closure properties of deterministic context-sensitive languages

There does seem to be a lot of information regarding the closure properties of both deterministic context-free and nondeterministic context-sensitive languages. However, the literature is almost mute ...
5
votes
2answers
107 views

Can real-time deterministic multicounter automata recognize the marked palindrome language?

Consider the marked palindrome language which is defined as MPAL=$\{ w\#w^r | w \in \{a,b\}^* \}$. It is easy to recognize MPAL using only a single stack. My question is whether MPAL can be ...
0
votes
0answers
112 views

Is there an algorithm to find whether 2 combinators form a Turing-complete system?

It is known that K = (λx.(λy.x)) and S = (λx.(λy.(λz.((x z) (y z))))) define a turing complete system, and we know procedures to ...
10
votes
1answer
602 views

Decide the existence of a string homomorphism

Consider the following problem: Given two strings x,y, decide whether there exists a string homomorphism f such that f(x)=y. It is easy to show that this problem is in $NP$. Are there other ...
14
votes
2answers
269 views

Does XOR automata (NXA) for finite languages benefit from cycles?

A non-deterministic Xor automata (NXA) is syntactically an NFA, but a word is said to be accepted by NXA if it has an odd number of accepting paths (instead of at least one accepting path in the NFA ...
5
votes
2answers
207 views

Bounds on size of self-concatenation of Finite Languages

Given a finite language $L$ with $|L|$ number of elements, what is $|L^i|$ (the language $L$ concatenated with itself $i$ times)? If there is no exact result, is there an upper/lower bound? Define ...
5
votes
1answer
138 views

What is the importance of linear languages?

What is the point of linear languages? They appear to be an intermediate set of languages in between regular and context-free languages, but do they have any useful or nice properties that either have ...
3
votes
0answers
130 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 ...
10
votes
0answers
211 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 ...
5
votes
1answer
137 views

What language $L \in NCM$ has $\overline{L} \not \in NCM$?

$NCM$, the class of non-deterministic reversal-bounded counter machines, has a lot of interesting dependability and closure properties. It's known that, unlike the deterministic version, NCM is not ...
6
votes
1answer
149 views

Bounds on the size of NFA for $r$-skip $k$-distinct language

This question is about an extension of a language discussed in this question. We define the $r$-skip $k$-distinct language as follows: $$L_{r,k}=\{\sigma_1\sigma_2\cdots \sigma_{rk}\in\Sigma^{rk} | ...
0
votes
0answers
108 views

In what complexity classes other than $NP$ are these problems related to unary languages?

If I remember correctly saw this reduction in a paper can't find at the moment. Consider the following NP-complete variation of the Subset Sum problem. Given a set of positive integers ...
4
votes
1answer
220 views

What characterizations exist for the grammars that can express subsets of the context-free languages?

It is well known that CFGs and PDAs are equivalent, and there has been extensive research about the relationship between deterministic pushdowns and $LR(1)$ grammars, as $DCFL$ is a subset of $LR(1)$. ...
6
votes
2answers
127 views

Are deterministic context-free languages closed under outfix (or other erasing operations)

Define the outfix of a language $L$ to be $Outf(L) = \{xy \mid \exists z. xzy \in L \}$. Are any known results about whether deterministic context-free languages are closed under this operation, or ...
20
votes
3answers
317 views

Complexity of intersection of regular languages as context-free grammars

Given regular expressions $R_1, \dots, R_n$, are there any non-trivial bounds on the size of the smallest context-free grammar for $R_1 \cap \cdots \cap R_n$?
2
votes
1answer
318 views

Natural examples of context-sensitive languages from practice

I am looking for natural examples of context-sensitive languages from practice. For example, reasonable answers could include grammar syntax of a programming language, or encoding of certain ...
1
vote
0answers
63 views

Can the definition of ambiguity of CFG be extended to CSG?

Usually,ambiguity of grammar is defined for constext-free languages and grammars,sometime it is extended to indexed languages and grammar,but the extension of definition of the definition is same ...
13
votes
4answers
373 views

What notable automaton models have polynomially-decidable containment?

I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
15
votes
1answer
370 views

Can constant ambiguity reduce the state complexity of a regular languages?

We say that NFA $M$ is Constantly Ambiguous if there exist $k\in \mathbb{N}$ such that any word $w\in \Sigma^*$ is accepted by either $0$ or (exactly) $k$ paths. If automaton $M$ is constantly ...
8
votes
1answer
139 views

Asymptotic density of ambiguous context-free grammars (CFGs)

What is the ratio of ambiguous CFGs to all CFGs? Since both sets are countably infinite the ratio is not well-defined. But what about the asymptotic density: $$\lim_{n \mapsto \infty}\frac {\# ...
-1
votes
2answers
92 views

Looking for menu-driven coding editor based on a programming language state machine [closed]

I'd like to know whether an application development environment exists that uses a menu-driven coding editor that employs a programming language state machine. This would mean that commands, variable ...
4
votes
1answer
528 views

What are the relationship and difference between ambiguous grammars and non-deterministic ones?

Intuitively, I had assumed that ambiguous grammars were roughly the same as non-deterministic grammars. According to Wikipedia however, this is false: there are non-deterministic unambiguous CFGs ...
0
votes
0answers
62 views

Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form?

Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form? I cannot find an reference.
21
votes
1answer
359 views

Languages recognized by polynomial-size DFAs

For a fixed finite alphabet $\Sigma$, a formal language $L$ over $\Sigma$ is regular if there exists a deterministic finite automaton (DFA) over $\Sigma$ which accepts exactly $L$. I am interested in ...
8
votes
1answer
239 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 ...
8
votes
1answer
298 views

Lower bound for NFA accepting 3 letter language

Related to a recent question (Bounds on the size of the smallest NFA for L_k-distinct) Noam Nisan asked for a method to give a better lower bound for the size of an NFA than what we get from ...
4
votes
3answers
201 views

Regular languages under change of encoding

Consider a regular language $L$ with alphabet $\Sigma = \{0,1\}$. Can we say that the set of strings in $L$ (representing non-negative integers in binary encoding) when represented in some other ...
12
votes
2answers
198 views

Reference for Dyck languages being $\mathsf{TC}_0$-complete

Dyck languages $\mathsf{Dyck}(k)$ is defined by the following grammar $$ S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon $$ over the set of symbols ...
1
vote
2answers
131 views

Tool for specifying operational semantics for given formally specified programming language

I am trying to translate code from one programming language into another (to be specific - from RuleML to Drools, but other pairs can be expected as well) and it would be nice to know - whether there ...
11
votes
2answers
338 views

Why is linearizability a safety property and why are safety properties closed sets?

In Chapter 13 "Atomic Objects" of the book "Distributed Algorithms" by Nancy Lynch, linearizability (also known as atomicity) is proved to be a safety property. That is to say, its corresponding trace ...
5
votes
2answers
154 views

Higher order Quines - when do super Quines exist?

The normal Quine - a program that prints its own code - is a special case of an n-Quine. An n-Quine is a program that prints code for a different program that after n iterations of printing and ...
16
votes
0answers
224 views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
10
votes
2answers
218 views

The number of states of local automata

A deterministic automaton $\mathcal A = (X, Q, q_0, F, \delta)$ is called $k$-local for $k > 0$ if for every $w \in X^k$ the set $\{ \delta(q,w) : q \in Q \}$ contains at most one element. ...
11
votes
2answers
350 views

How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?

Unambiguous Finite Automatons (UFA) are special type of non-deterministic finite automatons (NFA). A NFA is called $unambiguous$ if every word $w\in \Sigma^*$ has at most one accepting path. This ...
4
votes
1answer
72 views

The polynomial languages and ordered syntactic monoids

A polynomial language is a languge which could be represented as the finite union of languages of the form: $$ A_0^* a_1 A_1^* a_2 \cdots a_k A_k^* \quad a_i \in X, A_i \subseteq X $$ Such an ...
2
votes
1answer
197 views

Computing the Syntactic Congruence

The syntactic monoid of a language $L \subseteq X^*$ is defined as the monoid obtained from the congruence relation $$ u\ \tilde{}\ v \ \mbox{ iff }\ \forall x,y \in X^* : xuy \in L \leftrightarrow ...
3
votes
0answers
112 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, ...