Questions tagged [fl.formal-languages]
formal languages, grammars, automata theory
86
questions with no upvoted or accepted answers
2
votes
0answers
56 views
Regular Tree Languages are closed under quotient?
The Wikipedia page for Regular Tree Grammars notes that if $L_1$ and $L_2$ are regular tree languages, than $L_1 \setminus L_2$ is as well. However, it doesn't define this quotient operation for trees,...
2
votes
0answers
36 views
A class of languages admitted by a class of grammars equivalent to $\mathbf{PR}$?
Is there a class of languages $L(G)$ admitted by a class of phrase structure grammars $G$ equivalent to $\mathbf{PR}$? (the class of primitive recursive languages = $\mathbf{LOOP}$)?
In greater ...
2
votes
0answers
82 views
Is there a DCSL that cannot be recognized in O(n^2) steps by a deterministic LBA?
Is there a context sensitive language $L$ so that $L$ cannot be recognized by a deterministic linear bounded turing machine in $O(n^2)$ steps, but still can be recognized by a deterministic LBA?
The ...
2
votes
0answers
92 views
Proof of the equivalence of Muller automata and Parity (or Rabin chain) automata
Let $A$ be some finite alphabet and $\mathcal A = (Q, \delta, q_0)$ be some determinisitic finite automaton. Then $\mathcal A$ accepts infinite words $\xi \in A^{\omega}$ according to the Muller ...
2
votes
0answers
81 views
What is the class of the languages recognized by PCREs?
I have been considering building a tool that would convert regexes between the various syntaxes (BRE, ERE, PCRE). It is obvious that PCREs are too strong for the is-regular problem to be decidable, ...
2
votes
0answers
203 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 ...
2
votes
0answers
138 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 ...
2
votes
0answers
777 views
What is the relationship between the number of states in Quantum Finite Automata and the number of non-regular languages they can recognize?
It is has been shown that Quantum Finite Automata can recognize at least some non-regular languages. What is the relationship between the number of states in a qfa and the number of non-regular ...
2
votes
0answers
210 views
Fast weighted intersection algorithm for CFG and FSA with self loops but no other circles?
We all know that arbitrary CFG and FSA can be intersected using the Bar-Hillel Construction, whose time complexity is unfortunately too expensive. On the other hand, there are efficient algorithms ...
1
vote
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(...
1
vote
0answers
44 views
Is there an unambiguous grammar that has no left recursion or left factors, but is not in $LL(1)$?
I know that, for a grammar $G$ to belong to $LL(1)$, it is necessary that
$G$ is not ambiguous; that is, every sentence has a unique parse tree in $G$.
$G$ has no left recursion; that is, we can't ...
1
vote
0answers
62 views
Rational power series over $\mathbb N \cup \{\infty\}$, rationality of singular part
Let $\Sigma$ be a finite alphabet, and consider the formel power series over $\Sigma$ considered as non-commuting variables with coefficients in the semiring $\mathcal N := \mathbb N \cup \{\infty\}$ ...
1
vote
0answers
58 views
What is the interpretation of an infinite formal context-free grammar?
Let $L$ be a language as follows:
$$
\begin{align*}
L &::= a\ |\ L^{*}\\
\end{align*}
$$
Now, suppose I apply some sort of transformation $T : N \rightarrow N$ where $N$ is the set of non-...
1
vote
0answers
33 views
Inductive definition of language operators like the set of all permutations of a word came from the shuffle operator
Let $X$ be a finite alphabet. Given two words $u, v \in X^{\ast}$ the shuffle operator is defined to be
$$
u || v := \{ u_1 v_1 u_2 v_2 \ldots u_n v_n : 1 \le i \le n, u_i, v_i \in X^{\ast}, u = u_1 \...
1
vote
0answers
102 views
Possibly small circuit complexity class containing REG?
What is the smallest well-known Boolean-circuit complexity class containing all the regular languages over the binary alphabet {0,1}?
If we believe Theorem 2 in
Koucký, Circuit Complexity of ...
1
vote
0answers
78 views
What logic(s) exist for attributing belief?
I'm looking for an appropriate formalism to represent "traceability" in claims, especially connecting conclusions to source materials in a rigorous way. For example, I'd like to be able to represent ...
1
vote
0answers
41 views
Range concatenation grammars which are unambiguous as (and are NOT CFL)?
Are there any range concatenation grammars that
generate only one possible parse tree
are not also context-free?
1
vote
0answers
113 views
Relation between MDPs and non-deterministic finite automatons
I'm confused as to the relation (computability-wise) between markov decision processes and NFAs. Are finite state MDPs expressible as regular grammars? If so, are markov decision processes thus ...
1
vote
0answers
98 views
If for every non-terminal in a cs-grammar there exists an obligatory rule, does this alter the language of derivable strings
I am reading Chomsky's article Three models for the description of language, one of the earliest papers where context-free and context-sensitive grammars are mentioned. Essentially what he calls ...
1
vote
0answers
140 views
Why is an automaton on finite words co-deterministic iff its transitions are co-deterministic
In the article Automata and semigroups recognizing infinite words an automaton is specified by $\mathcal A = (Q, A, E, I, F)$ where $I$ is a set of initial states and $F$ a set of final states, $Q$ ...
1
vote
0answers
57 views
Grammars whose LR automata have singleton item sets?
The states in LR parsers correspond to sets of items (ie, sets of productions from the original grammar, with a "dot" marking how far into the rule the parser has gotten). In general, states ...
1
vote
0answers
86 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.
1
vote
0answers
98 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 K\subseteq\...
1
vote
0answers
39 views
Determine whether a categorical grammar is minimal concerning lexical entries
In order to compare the descriptional complexity of context-free and (combinatoric) categorical I need a way to check if a categorical grammar of a formal language is minimal concerning lexical ...
1
vote
0answers
92 views
Automatic structures/functions: Is (Z,+) under a unary representation automatic?
The group $(\mathbb{Z}, +)$ is automatic (ala Khoussainov) when using the "standard" representation in a decimal base. But if I want to use a different representation of Z, encoding my integers with ...
1
vote
0answers
191 views
Dynamic k-shortest paths in a weighted transducer
I'm looking for references relating to dynamically computing the k-shortest output paths through a stochastic, acyclic, weighted transducer that is being constructed on-the-fly.
In this scenario ...
1
vote
0answers
643 views
Strategy for grammar derivation of a formal language
I wonder, whether there is any strategy/ies for grammar derivation of a formal language. I'd be thankful, if you give me some hints, tips on how should one "think" trying to find a grammar. I'm ...
1
vote
0answers
177 views
LALR grammars subsets
If LR(0) condition for a grammar G is formulated as follows:
Every state is either reduction or a shift state and it can't be both at the same time
if it is a reduction state, it contains exactly one ...
1
vote
0answers
181 views
Edit-Distance of weighted automata
I'm trying to understand "Edit Distance of Weighted Automata" by Mehryar Mohri: [83], [93] and [99] at http://www.cs.nyu.edu/~mohri/pub/ (they are virtually identical so which of them doesn't matter).
...
1
vote
0answers
313 views
Restricted read twice BDDs and context free grammars
Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1]
Quote:
Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled,
and a formal ...
0
votes
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 ...
0
votes
0answers
49 views
Incompleteness and term extraction
Is there a formalization, which from a proof that a system includes enough arithmetic extracts an arithmetic sentence in the language of PA, which is not provable in the given system? Imagine the ...
0
votes
0answers
160 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 ...
0
votes
0answers
159 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 $S=\{x_1,\...
0
votes
0answers
125 views
Given a sequence find the shortest reg exp that generates it?
I'm looking for a way to find the smallest possible regular-expression that accepts a sequence.
To make it interesting I don't want any stars(Kleene stars) and preferably no wildcards?
For instance ...
0
votes
0answers
176 views
Classification of Saturated LL(1) Grammars
By saturated I mean that the grammar accepts every possible string
that can be constructed from the terminal set. So the parse table would
be full of valid entries, no error entries at all. Can such a ...
