formal languages, grammars, automata theory
0
votes
0answers
84 views
Is there a way to transform a Turing machine into an oblivious turing machine that decides the same langauage?
Suppose you have turing machine M that decides L. Is there a simple way to convert this turing machine into an oblivious turing machine M' that decides the same language? My intuition says yes but i ...
-4
votes
0answers
24 views
Proof that the regular languages are closed under string homomorphism [migrated]
Where can I find a proof of this? Thanks!
1
vote
1answer
48 views
Deterministic Buchi + its complement covers LTL?
It is well known that deterministic Buchi automata (DBA) are less expressive than non-deterministic Buchi automata (NBA), and in particular DBA are not enough to cover linear temporal logic (LTL). ...
7
votes
0answers
94 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) ...
1
vote
0answers
73 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
1answer
135 views
Is the gist of English (or any equally familiar natural language) context-free? [closed]
When I say 'equally familiar natural language', I hope to ignore languages such as Arabic and Hebrew, of which I know absolutely nothing save an alphabet in the latter case.
I am doing research in ...
2
votes
0answers
56 views
$\omega$-regular properties of a 2-state Markov Chain
Let $X$ be a Markov Chain on a state space $\{0,1\}$ with a transition matrix
$$
P = \left(
\begin{align}
1-p & &p
\\
q & &1-q
\end{align}
\right)
$$
with both $p,q \in (0,1)$ so in ...
6
votes
1answer
114 views
Measurable language which is not $\omega$-regular
Let $\Sigma$ be a finite alphabet and let $\Sigma^\omega$ be the set of all infinite words over $\Sigma$. Consider
$$
d(x,y):=2^{-\min(n \in \Bbb N_0:x_n\neq y_n)}
$$
to be the metric on ...
10
votes
2answers
271 views
Does there exist an extension of regular expressions that captures the context free languages?
In many papers involving context-free grammars (CFGs), the examples of such grammars presented there often admit easy characterizations of the language they generate. For example:
$S \to a a S b$
...
13
votes
2answers
424 views
minimizing size of regular expression for finite sets
It is known that minimizing the size of a regular expression is PSPACE-complete even if we have a DFA as the language's specification.
What are the results if the language is finite?
One can ...
5
votes
0answers
133 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 = ...
-1
votes
0answers
75 views
How does “δ:Q×Σ→Q” read in the definition of a DFA (deterministic finite acceptor)? [closed]
How do you say "δ:Q×Σ→Q" in English? Describing what "×" and "→" mean would also help.
7
votes
0answers
186 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 ...
114
votes
10answers
35k views
What is the enlightenment I'm supposed to attain after studying finite automata?
I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we ...
6
votes
0answers
120 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 ...
5
votes
0answers
112 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 ...
0
votes
0answers
64 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 ...
9
votes
2answers
189 views
The significance of state complexity in automata and regular languages?
I'm reading "Concatenation of Regular Languages and Descriptional Complexity" by Galina Jiraskova, 2009 on the state complexity resulting from concatenation of two regular languages ( by Galina ...
5
votes
1answer
163 views
Non-isomorphic minimal non-deterministic finite automata
Can somebody provide an example of two equivalent (recognizing the same language) minimal non-deterministic automata (NFA) which are not isomorphic?
-3
votes
1answer
366 views
Name for terminals on the left-hand side of grammar rules? [closed]
Consider rules as they are used for context-sensitive languages:
$\alpha A \beta \rightarrow \alpha \gamma \beta$
If $\alpha$ is always empty, we have right-context sensitive grammars:
$A \beta ...
0
votes
0answers
68 views
Generalizing a set of positive and negative examples through DFAs [duplicate]
Possible Duplicate:
Is finding the minimum regular expression an NP-complete problem?
Let $\Sigma$ be an alphabet. Let $P$ and $N$ (the set of positive and negative examples) be two ...
4
votes
1answer
105 views
Getting an automaton from set of words in and out of a language [duplicate]
Possible Duplicate:
Is finding the minimum regular expression an NP-complete problem?
Let's suppose that I have an unknown language $\mathcal L$, I know only two (particularly large) sets ...
0
votes
1answer
128 views
Implicit Non-deterministic Buchi determinization
I am doing implicit Buchi determination for LTL logic in hardware where the combinational logic represents the set of states.
But instead of using acceptance states, I am using final state (as in ...
7
votes
1answer
156 views
Regular expressions of families of regular expressions
I was reading about the Star Height Problem and noticed that Eggan's family of regular expressions follows a simple pattern which can be described by a regular expression. My question is: are there ...
8
votes
1answer
158 views
Rational Functions and CFL
In my work arose the problem of classification CFL under rational functions images. In other terms, what class of languages form languages $T(L)$ , for fixed context free language $L$ and ...
5
votes
1answer
103 views
Two way deterministic multihead counter automata or logspace TM with counter
Is that known something about languages recognized by two-way deterministic multihead counter automaton or logspace TM with counter (equivalent model)? This class called Aux2DC in my advisor's paper. ...
3
votes
0answers
134 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 ...
0
votes
1answer
166 views
Can abstract syntax trees be unparsed in subexponential time?
Abstract problem description
The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST, i.e. ...
6
votes
0answers
408 views
minimizing size of regular expression
Suppose we have a regular language specified by a regex, for example, (ab|ac)* and we wish to find an equivalent regex with the minimal number of symbols, (a(b|c))*. Is there any efficient way to do ...
0
votes
0answers
112 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 ...
11
votes
0answers
148 views
Unary languages recognized by two-way deterministic counter automata
2dca's (two-way deterministic one-counter automata) (Petersen, 1994) can recognize the following unary language:
\begin{equation}
\mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace.
...
-5
votes
2answers
205 views
Deterministic CFL closure Property Homomorphism [closed]
I tried to research the following question with no results: Can you find one example where the following holds true:
Let L = {xxxxxxx} be a deterministic-context-free Language and Let h(...) = xxxxx ...
5
votes
1answer
152 views
Minimal Number of Symbols in Context-Free Grammar for a Special One-Letter Language
Given is the language
$$L_n = \{a^n\},$$
where $n$ is a natural number and $a$ is a letter. What are the productions/rules of a minimal context-free grammar according to the number of symbols of the ...
0
votes
0answers
193 views
Determining if a grammar can be converted to LL(1)/LL(k) [closed]
I'd like to know if there is a way to determine if a context-free grammar can be converted to
a LL(1) grammar
a LL(k) grammar, whatever the value of k (so the algorithm should give the value of k)
...
13
votes
1answer
850 views
Sufficient conditions for the regularity of a context-free language
It would be nice to collect a list of conditions that imply that a context-free language L
is regular, i.e. conditions of the form:
"if a given CFG/PDA has property P, then its languages is regular"
...
3
votes
0answers
254 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 ...
10
votes
2answers
431 views
Büchi automata with acceptance strategy
The problem
Let $A=\langle \Sigma, Q, q_0,F,\Delta\rangle$ be a Büchi automaton, recognizing a language $L\subseteq\Sigma^\omega$.
We assume that $A$ has an acceptance strategy in the following sense ...
14
votes
3answers
562 views
Regular languages from category-theoretical point of view
I noticed that regular languages over the alphabet $\Sigma$ can be naturally thought of as a poset, and indeed a lattice. Moreover, concatenation together with the empty language $\epsilon$ defines a ...
3
votes
1answer
175 views
Automatically creating weighted DFAs penalizing sequences of subsets of the alphabet
For a given finite alphabet $\Sigma$, my goal is to write an algorithm
that receives as input a sequence $V=V_{1}V_{2}\dots V_{n}$ of subsets
($V_{i}\subseteq\Sigma$), and returns a weighted ...
6
votes
0answers
197 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
0answers
339 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 ...
1
vote
2answers
251 views
are there fixed context sensitive grammars which are PSPACE complete?
wikipedia entry says without reference that
"There are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete."
This is stronger than saying that CSG is ...
4
votes
1answer
146 views
Contract preservation using grammars
I am exploring using annotated grammars to formalize and enforce parts of contracts between nodes in a distributed application.
I've found a number of articles on languages for specifying fairly ...
0
votes
1answer
123 views
Does there exist a CAS for formal language theory?
I need support for: grammars, equivalence classes, finite sets, and some smallest grammar approximation functions.
4
votes
0answers
133 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 ...
0
votes
1answer
148 views
Decide if a given sequence is regular or context-free
Given a sequence s (or a finite set of sequences) I would like to know if this was generated by a regular or by a context-free (supposes these are the only options) grammar.
Of course, this is an ...
9
votes
3answers
442 views
1-way Quantum Finite Automata Example Question
I'm attempting to clarify my understanding in the example presented in Section 2.2 of 1-way Quantum Finite Automata: Strengths Weaknesses and Generalizations (this alternative link may also be ...
2
votes
0answers
96 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 ...
2
votes
1answer
94 views
Is state splitting the LR equivalent of LL nonterminal replication
The grammar classes SLR and strong LL are similar in that they both use FOLLOW sets to resolve conflicts. For still unresolved conflicts, state splitting always works for SLR grammars, if the grammar ...
7
votes
1answer
656 views
computing the minimal NFA for a DFA
Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known ...
