Questions tagged [automata-theory]

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

Filter by
Sorted by
Tagged with
2
votes
0answers
73 views

WFSA over hyperreals

Are there any works where authors tried to define weighted finite state automata over hyperreals (or a similar object allowing for infinite and infinitesimal values) in an attempt to make automata ...
2
votes
1answer
390 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 ...
4
votes
1answer
225 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 ...
6
votes
3answers
529 views

Can words in regular languages be generated by automata in a unique way?

If $L\subset \Sigma^\ast$ is a regular language then it is known that we can find a directed graph (aka automaton) $G$ with edges labelled with symbols from $\Sigma$, an ‘initial’ vertex, and a set of ...
3
votes
0answers
166 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
369 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 ...
6
votes
0answers
463 views

Generalized sequential machine synthesis subject to language equivalence/inclusion and reachability

A generalized sequential machine (GSM) is a generalization of a Mealy machine where on each transition one input symbol is read and 0 or more output symbols are written. As in a Mealy machine, we ...
4
votes
0answers
82 views

Sub optimal regex equivalence

Regex Equivalence is a hard problem which in general takes exponential space and exponential time. Are there any approximation/sub-optimal algorithms with some theoretical guarantees over equivalence ...
-2
votes
1answer
586 views

Intersection between context-free and context-sensitive language decidability [closed]

I'm trying to find a formal proof of the following fact: Given a context-free language, say $L_1$, and a context-sensitive language, say $L_2$, it is NOT decidable if their intersection is empty ($...
3
votes
0answers
110 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 \...
10
votes
2answers
3k views

2DFA that requires many states in equivalent DFA?

Is there a 2DFA with $n$ states (where $n$ is nontrivial, say at least 4) that requires at least $2^n$ states to simulate using any DFA? A two-way DFA (2DFA) is a deterministic finite-state automaton ...
0
votes
1answer
86 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 I....
1
vote
4answers
418 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 ...
3
votes
0answers
103 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 L(\...
0
votes
1answer
172 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$?
4
votes
1answer
108 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 ...
5
votes
3answers
636 views

Formal definition of parser?

I'm looking for an accepted, formal definition of a parser as function $f$ returning an AST, but I cannot find any reference in literature; all I can find is the definition of a recognizer as a ...
2
votes
1answer
515 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 ...
37
votes
14answers
22k views

How practical is Automata Theory?

There is always a way for application in topics related to theoretical computer science. But textbooks and undergraduate courses usually don't explain the reason that automata theory is an important ...
4
votes
3answers
422 views

How to minimize a FSM transducer?

In contrast to FSM minimization which is well studied with various algorithms, theorems and has many practical applications, I'm looking for any nontrivial insight, analysis and references to the ...
1
vote
0answers
94 views

Properties of the number of copies of an NFA in each state

For an NFA $A$ with $n$ states and a word $w$, we can associate an $n$-dimensional vector $v_w$ with entries in $\mathbb{N}\cup\{0\}$ denoting the number of copies of the NFA in each state after ...
3
votes
0answers
209 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 ...
9
votes
1answer
334 views

Multi-language DFA minimisation

I'm interested in a slight generalisation of DFA. As usual we have state-set $Q$, finite alphabet $\Sigma$, a $\Sigma^*$-action defined on $Q$ by $\delta : Q\times\Sigma\rightarrow Q$, and initial ...
14
votes
3answers
738 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 ...
-4
votes
1answer
307 views

Can I show algebraically that this regular expression accepts all binary strings?

The task is to prove that (0+1)* and 0*(1.0*)* are equivalent. 1. http://rubular.com/r/K9Hp9tU6px 2. http://rubular.com/r/N8VpoEcch4 EDIT: Forgot that + was ambiguous here! I want to prove that the ...
7
votes
3answers
602 views

Algorithm for ranking members of a regular language?

A little while back, I was reading a paper that mentioned a method for computing an integer 'rank' for a particular string $s \in L$ where $L$ is some regular language. This rank uniquely determines ...
7
votes
0answers
139 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
1answer
228 views

Measurability of an $\omega$-regular language

It the previous question of mine I put a reference which shows that any $\omega$-regular language over the alphabet $\Sigma$ is a Borel subset of $\Sigma^\omega$. I am not sure whether the reference I ...
6
votes
0answers
177 views

Separation of the states of a deterministic omega-automaton by looping words taken from a regular language of non-empty words

Consider a deterministic transition structure having states in set $X$ and transition function $\rightarrow$, and an initial state $x \in X$. This structure is intended to be part of an automaton ...
6
votes
0answers
147 views

Are k+1 heads better than k for multiread finite automata?

Consider the deterministic (resp. non-deterministic) one-way finite automaton that is defined in the usual way except that it has k heads and in each step can decide which head to move. (It is allowed ...
1
vote
0answers
72 views

Vector representation of probabilistic automaton

Suppose we have $N$ states $q_i$, $0\leq i<N$ Suppose we have $N\times N$ probability matrix $p_{ij}$, $0\leq i<N$, $0\leq j<N$, And suppose a machine, which is being in state $q_i$ then ...
2
votes
1answer
107 views

Is it decidable whether the langauge accepted by a reversal-bounded counter machine is deterministic?

I'm wondering if anyone can point me to either an algorithm or an undecidability proof for the following question: Given a non-deterministic reversal-bounded multicounter machine $M$, is there some ...
4
votes
1answer
723 views

Minimal context-free grammar for a regular language

Are there any algorithms for solving exactly the following question? Given a regular language L, represented as a finite automaton say, what is a CFG with minimal number of nonterminals that generates ...
17
votes
2answers
418 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. \end{...
6
votes
3answers
417 views

Simplification of weighted NFA

What options does one have for the simplification (meaning reduction in the number of states) of weighted NFA over the probability semiring? From my understanding one can determinize, and then ...
2
votes
1answer
97 views

Are Reversal-bounded Multicounter Machines closed under reversal?

This is a problem I have found very difficult to solve, given how the two different uses of "reversal" confuses search engines. Reversal-bounded multicounter machines are described at length in his ...
12
votes
1answer
330 views

Is there a book/survey-paper outlining language class hierarchies, closure properties, etc

I'm currently doing some Formal Language research involving classes of languages above Regular but below Context Free. I'm looking at things like Reversal-Bounded Multicounter Machines, Single-stack ...
6
votes
3answers
401 views

Chomsky hierarchy for tree structures

I know of the Chomsky hierarchy, which concerns the expressive power of grammars to recognize languages $L \subseteq \Sigma^*$ made of words on an alphabet $\Sigma$. Is there a similar hierarchy for ...
2
votes
1answer
299 views

Number of accepting path of a non deterministic automaton

I have a question that seems to me really natural and have probably already been studied. But keyword search on this site or google does not seems to help me to find any relevent paper. I have got a ...
7
votes
1answer
217 views

Complete problems and universal simulator machines

I'm trying to get straight in my mind the relation between complete problems and universal simulator machines. Some notions of computability have universal machines (Turing-computability) and some ...
-1
votes
1answer
103 views

Constructing automata with the same traces, but where a CTL-formula is not equally satisfied [closed]

Hard to put this question in a short title. As part of a self-exercise, I'm trying to solve 6.15b of Principles of Model Checking by Baier and Katoen. You're supposed to prove that there does not ...
7
votes
1answer
1k views

Photo of «Introduction to automata…» by Hopcroft and Ullman '79 cover?

Where can I get the photo of “Introduction to automata theory, languages and computation” by Hopcroft and Ullman '79 (first edition) cover in order to be able to read all the phrases placed on the ...
3
votes
0answers
304 views

Name this digraph

I am trying to track down the name of this digraph and some references: You take all members of the transformation semigroup on $n$ elements, $T_{n}$. For two members $x$ ,$y$ ; if $x$ is in the ...
2
votes
0answers
776 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 ...
7
votes
1answer
324 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 $\Sigma^\...
9
votes
2answers
378 views

Are there families of formal languages known to be truly PAC learnable?

I specifically mean language families that admit arbitrarily long strings -- not conjunctions over n bits or decision lists or any other "simple" language contained in {0,1}^n. I am asking about "...
4
votes
2answers
871 views

Finite state transducer that sorts

Is it possible to sort a string of arbitrary length with a finite-state transducer? How big would this transducer be (the smaller the better)? (I'm not a computer scientist, so less technical answers ...
7
votes
0answers
150 views

Size complexity of probabilistic two-way automata for a Boolean function

I'm interested in computing Boolean functions $f:\{0,1\}^n\rightarrow\{0,1\}$ with two-way finite automata and I will measure the complexity of a Boolean function by the number of states for the ...
1
vote
2answers
336 views

Find minimum number of transformations to transform from input to target string

Given that I have an input string, for example: aab And I am given a target string, for example: bababa And then I am given a ...
-1
votes
0answers
117 views