Questions tagged [automata-theory]

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

Filter by
Sorted by
Tagged with
3
votes
0answers
214 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 ...
-4
votes
1answer
312 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
0answers
141 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
3answers
609 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
1answer
232 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
178 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 ...
16
votes
1answer
390 views

Are there variants of visibly pushdown automata that allow pushing of words onto the stack?

I'm wondering, are there any papers or research dealing with visibly pushdown automata, but allowing words, rather than single letters, to be pushed onto the stack. Alternately, a construction which ...
6
votes
0answers
148 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 ...
13
votes
4answers
692 views

(N)DFA with same initial/accepting state(s)

What is known about the class of languages recognized by finite automata having the same initial and accepting state? This is a proper subset of the regular languages (since every such language ...
5
votes
1answer
221 views

Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters?

I was reading this paper, about the complexity of decision problems for reversal bounded counter machines. I got to Theorem 1 on Page 6. The theorem shows that there's a log-space NTM which can ...
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
734 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 ...
3
votes
0answers
232 views

Providence of pumping lemmas for regular languages

I'm looking to track down who discovered the following pumping lemmas for regular languages. (where $p$ is the pumping constant.) Reg($L) \rightarrow \exists p\forall w(\in L) \forall u_1u_2v(\in \...
6
votes
3answers
423 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
331 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
403 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
307 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 ...
-1
votes
1answer
106 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
220 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 ...
3
votes
1answer
295 views

Deterministic Büchi + its complement covers LTL?

It is well known that deterministic Büchi automata (DBA) are less expressive than non-deterministic Büchi automata (NBA), and in particular DBA are not enough to cover linear temporal logic (LTL). ...
3
votes
0answers
305 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 ...
8
votes
1answer
350 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^\...
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 ...
4
votes
2answers
890 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 ...
1
vote
2answers
340 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 ...
10
votes
1answer
340 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 ...
-1
votes
0answers
117 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.
1
vote
1answer
406 views

How to show that ECTL* is more expressive than CTL* $\cup$ Büchi (with an example)

I am looking for a preferably simple property that is expressible in ECTL* but not in CTL* and not in Büchi, with a citable reference to the proof. Details of what I've tried: I've tried a ...
2
votes
2answers
235 views

Alternating automata

In the paper Fast LTL to Buchi Automata Translation (2001, Gastin and Oddoux) the authors, while defining co-Buchi alternating automata define $\Sigma’= 2^\Sigma$ where $\Sigma$ is the alphabet. ...
4
votes
2answers
319 views

Inductive definition of ECTL*: how are recursive formulas forbidden?

In [1], the extended computation tree logic ECTL* is inductively defined as the propositional formulas over all E($A(F_1,..F_n)$), where E is the existential path quantifier and $A$ some Büchi ...
4
votes
1answer
422 views

Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions

If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $ \Theta \left( 2^n/...
12
votes
1answer
717 views

The Cost of an Equivalence Query for DFA

Inspired by this question, I am curious about the following: What is the worst-case complexity of checking whether a given DFA accepts the same language as a given regular expression? Is this ...
11
votes
1answer
4k views

What algorithms exist for construction a DFA that recognizes the language described by a given regex?

All of my textbooks use the same algorithm for producing a DFA given a regex: First, make an NFA that recognizes the language of the regex, then, using the subset (aka "powerset") construction, ...
0
votes
2answers
172 views

iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation

A question partly inspired by a recent question[1] on the utility of FSMs: Years ago noticed the following property of FSM transducers with $\epsilon$-transitions (which allow an "empty" transition ...
5
votes
2answers
2k views

Why were Finite Automata and Turing Machines created?

It seems the creation of Turing Machines and finite automata were apart by at least 2+ decades. That is TMs don't really reference FAs for their working and vice versa; TMs and FAs were developed ...
248
votes
11answers
95k 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 ...
12
votes
2answers
434 views

Why is the state of a FSM traditionally denoted $q$?

While teaching how to implement FSMs using synchronous logical circuits, I noticed an intriguing coincidence: in both the theoretical CS world, and in the electrical engineering world, "state" is ...
9
votes
0answers
145 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 ...
1
vote
0answers
90 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 ...
14
votes
3answers
749 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 ...
12
votes
2answers
527 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?
4
votes
1answer
214 views

State transducers for generating permutations

Let a finite alphabet $\Sigma$. Let $\mathcal{Reord_\Sigma}$ be the family of computable partial functions between the strings of this alphabet $r\,:\, \Sigma^*\, \rightarrow \Sigma^*$ with the ...
-3
votes
1answer
708 views

Minimal Turing Machine implementation / Von Neumann UC [closed]

I've written a small python program which implements a Turing Machine with a finite tape. It has a tape, a head, a state register and a set of transfer functions ("the program"). The difference to a ...
0
votes
0answers
77 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 disjoint ...
4
votes
1answer
175 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 of ...
0
votes
1answer
158 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 ...
6
votes
0answers
273 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 language?...