# Questions tagged [automata-theory]

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

354 questions
Filter by
Sorted by
Tagged with
228 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 ...
140 views

### A word anticorrespondence problem

A problem instance is a finite list of 4-tuples $(\alpha_1, u_1, v_1, \beta_1), ..., (\alpha_N, u_N, v_N, \beta_N)$, where $\alpha_i, \beta_i \in X$ come from a finite set, and each $u_i,v_i \in A^*$ ...
144 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 ...
151 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 ...
339 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 ...
533 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 ...
222 views

203 views

### What is the motivation behind defining Deterministic Looping Automata?

I was wondering about what could possibly be the motivation behind defining the deterministic looping automata? What puzzles me is that they accept a word iff they have a run on it! I believe they ...
545 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 ...
128 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 ...
1k views

### What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?

What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why? Details: http://en.wikipedia.org/wiki/Powerset_construction states that the worst-...
227 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 ...
274 views

### Why may the right hand sides in Chomsky Hierachy type 1 be larger?

I'm shaking my head because of this question, my Prof. didn't explain it. We have linear space limited automata and they have to satisfy for rules a -> b that |a| <= |b|. Why? I would have said, ...
159 views

### Is there any equation-based method for transforming Büchi-automata to omega-regular language?

I know there exists an equation-based method for transforming finite automata into regular language (or `regular expression'). The main idea is as follows. First we construct a set of equations ...
165 views

### Can real-time deterministic multicounter automata recognize the marked palindrome language?

Consider the marked palindrome language which is defined as MPAL=$\{ w\#w^r | w \in \{a,b\}^* \}$. It is easy to recognize MPAL using only a single stack. My question is whether MPAL can be ...
166 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 ...
1k views

### Emptiness of PDA without constructing the corresponding CFG

The emptiness problem for Context free Grammars(CFG) is well studied. The same holds for the equivalence problem between Pushdown Automata (PDA) and CFGs. Therefore, given a PDA, the straightforward ...
983 views

### Closure properties of deterministic context-sensitive languages

There does seem to be a lot of information regarding the closure properties of both deterministic context-free and nondeterministic context-sensitive languages. However, the literature is almost mute ...
283 views

### Equivalence problem for one-counter automata

I know that the equivalence problem for deterministic one counter automata is decidable, however does anyone know whether it is decidable for all one counter automata or just the deterministic ones? ...
177 views

### Useful equivalence relations on $X^{\ast}$ (like the Nerode and syntactic equivalence relations)

I want to have an overview of all the meaningful equivalence relations defined on $X^{\ast}$, in particular when the languages in question are regular. They typically arise in connection with the ...
138 views

### When does automaton stay unchanged after string homomorphism?

Suppose we have a string homomorphism $\varphi: \Sigma \rightarrow \Sigma^*$. Consider the languages in $\varphi(\Sigma^*)$ whose letters are elements of $\varphi(\Sigma)$, so here I do not want to ...
132 views

### Are PDAs without ϵ moves and with bounded stack operation as powerful as PDAs with them?

It is known that PDAs without $\epsilon$ moves are as powerful as PDAs with them. However, it seems to me that the proof allows several stack operations in one move. What happens if we allow at most ...
240 views

### Name for a special family of languages?

I was wondering whether there is a standard name in the literature for the following family $\mathcal{F}$ of languages over any finite alphabet $\Sigma = \{a_1,\ldots,a_k\}$: $\mathcal{F}$ consists ...
147 views

### Bounds on this Strategy for Separating Words

Question Given binary string $z \in \{0,1\}^n$, let $f(z)$ be the smallest integer $k$ such that there exists a DFA with $k$ states, such that reading $z$ from a specific starting state, we end at a ...
116 views

### Languages whose Parikh image is recognizable

Let $\Sigma$ be some alphabet, and $p : \Sigma^* \to \mathbb N_0^{|\Sigma|}$ the Parikh map. A formal language $L \subseteq \Sigma^*$ is called a slip-language, if $p(L)$ is a semilinear set. By ...