formal languages, grammars, automata theory

learn more… | top users | synonyms (2)

0
votes
1answer
33 views

Safety property as closed set [closed]

In the paper "the existence of refinement mappings", the formal definition of safety property is defined as closed set which is based on the definition of closed set: $\sigma|_m$ denote the prefix of ...
14
votes
2answers
209 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 ...
4
votes
2answers
181 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 ...
1
vote
0answers
61 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
111 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
175 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
131 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
143 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
70 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
198 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
102 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 ...
10
votes
0answers
74 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
142 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
49 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
337 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
358 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
127 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
68 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 ...
3
votes
1answer
144 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
41 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.
19
votes
1answer
265 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 ...
0
votes
0answers
51 views

An algorithm for extracting grammars given existing grammar

Let all the grammars of concern here be CFGs. Let $A$ be a grammar with rules $A^i \Rightarrow a_1^i \dots a_{n_i}^i, \ i = 1 \dots n$, where each $a_i^j$ is either a terminal in $\Sigma$ or a rule ...
7
votes
1answer
203 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
255 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
185 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
184 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
93 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 ...
10
votes
2answers
297 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 ...
4
votes
2answers
147 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 ...
15
votes
0answers
166 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
200 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
317 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
64 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
138 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
85 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, ...
0
votes
1answer
101 views

Adherence of languages and the Dyck language

Let $L \subseteq X^*$ and $X = \{a,b\}$ be a language of finite words, denote by $A(u)$ the prefixes of some word (finite or infinite), then the adherence $\mbox{Adh}(L)$ is defined to be the set of ...
1
vote
1answer
64 views

Assessing complexity of a language using subset relations

What makes a language hard in a computational sense is neither simply that it contains very few words(e.g. is finite) or that it contains a lot of words(e.g. is infinte) but rather an intricate ...
3
votes
0answers
91 views

Transfering properties from subsets of $X^*$ to subsets of $X^{\omega}$ by using the topology induces by Cantor space

A language $L \subseteq X^*$ is non-counting of order $n > 0$ iff for all $u,v, w \in X^*$ $$ uv^nw \in L \Leftrightarrow uv^{n+1} w \in L. $$ A $\omega$-language (set of infinite sequences) $L ...
0
votes
1answer
67 views

Difference between locally testable and it's boolean closure

A language $L$ is called i) locally testable in the strict sense iff there exists $P, S, I \subseteq X^*$ such that $$ w \in L \mbox{ iff } pref^k(w) \in P, suffix^k(w) \in S, infix^k(w) \subseteq ...
14
votes
1answer
240 views

Can a two counters machine decide $n^2$?

Can a standard two counters ($c_1,c_2$) machine with the following instructions: ...
3
votes
0answers
86 views

Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata

Let $\mathcal A$ be an automaton, then I define the following $\omega$-language accepted by $\mathcal A$: $$ L'(\mathcal A) := \{ \eta \in X^{\omega} : v \sqsubset \eta \mbox{ implies } v \in ...
1
vote
4answers
217 views

Questions about regular languages and their sublanguages

I am interested in the following questions and would be grateful if anyone could give me hints or point me to articles: 1) Given a regular language $L$, what are its regular sublanguages $L'\subseteq ...
9
votes
2answers
187 views

Smallest Boolean circuit to generate a language

Consider a non-empty language $L$ of binary strings of length $n$. I can describe $L$ with a Boolean circuit $C$ with $n$ inputs and one output such that $C(w)$ is true iff $w \in L$: this is ...
0
votes
1answer
106 views

Does every regular language contains a strictly locally testable language?

Let $L$ be an infinite regular language, then does there exists a strictly locally testable infinite language $P$ such that $P \subseteq L$?
1
vote
0answers
76 views

Formal languages induced by ultrafilters

Let $I$ be the set of all recursively enumerable languages over an alphabet $\Sigma$. Let $$S_\alpha=\{i\in I : \alpha\in i\}$$ for all $\alpha\in\Sigma^*$. Then $$E=\{S_\alpha:\alpha\in ...
4
votes
1answer
89 views

When does a set of infixes determine a set of ($\omega$-) words

If a have a set of finite infixes of a specific length, which $\omega$-languages are determined by them, and furthermore, when does a set of infixes determine a $\omega$-word uniquely. For example for ...
3
votes
3answers
1k views

Ambiguity in regular and context-free languages

I understand the following claims to be true: Two distinct derivations of a string in a given CFG may sometimes attribute the same parse tree to the string. When there are derivations of some string ...
0
votes
1answer
203 views

Has anyone mixed linear algebra with formal language theory in this way?

Let $G$ be the grammar: $$ S \rightarrow aAb \\ A \rightarrow aA + a + \epsilon $$ where $\epsilon$ is the empty string, $a,b$ are terminals and $S,A$ non-terminals with $S$ the start symbol. ...
-2
votes
1answer
80 views

Has anyone ever mixed strings in a language with position?

Let the alphabet $\Sigma$ be extended to include $\bullet$, the concatenation point character. Define concatenation of such strings to be: (by example): $$ s\cdot t = (\omega \bullet \gamma ) \cdot ...
2
votes
1answer
169 views

Closure Properties of Locally Testable Language

Are locally testable languages closed under complementation? I guess yes, because when I can decide membership by sliding a window of size $k$ over the word and looking if the $k$-length words ...