Questions tagged [automata-theory]

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

Filter by
Sorted by
Tagged with
17
votes
5answers
2k views

Ambiguity and Logic

In automata theory (finite automata, pushdown automata, ...) and in complexity, there is a notion of "ambiguity". An automaton is ambiguous if there is a word $w$ with at least two distinct accepting ...
-4
votes
3answers
521 views

Time-based mathematics or logic [closed]

The conventional systems of logic can only recognize or perform operations that transform or translate values in space. Ordinary logic treats time poorly through the necessity of translating all ...
10
votes
1answer
752 views

Closure of unambiguous context-free languages under pre- and postfix.

Let $L$ be a context-free language. Define $ppc(L)$ to be the pre- and postfix closure of $L$, in other words, $ppc(L)$ contains all of $L$'s prefixes and postfixes, and hence $L$ itself. My question: ...
19
votes
0answers
484 views

To what extent MSO = WS1S, when adding relations?

[This question has been asked on MathOverflow with no luck a month ago.] Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma =\{a_1, \ldots, a_n\}$, I define two ...
0
votes
3answers
216 views

A fsm with temporal events

I have defined a finite state machine Q = {Σ, S, s0, δ, F} where Σ = {'[r]equest', '[o]ut', '[i]n', '[e]nd'} S = {'[R]eady', '[I]nitiating', '[W]aiting', 'Re[C]eived', 'Re[S]...
16
votes
1answer
368 views

Compared growth of the number of syntactic classes and Nerode classes.

For a language L ⊆ Σ^*, define the syntactic congruence ≡ of L as the least congruence on Σ^* that saturates L, i.e. : u ≡ v ⇔ (∀ x, y)[xuy ∈ L ↔ xvy ∈ L]. Now define the Nerode equivalence as the ...
-2
votes
2answers
384 views

Can every non-deterministic finite automate be changed into one with only one acceptance state? [closed]

How can an arbitrary non-deterministic finite automate be converted into one with only one accept stage? If so, what is the proof that this can always be done?
30
votes
4answers
1k views

Are there "small" machines which can efficiently match regular expressions?

It's well-known that a regular expression can be recognized by a nondeterministic finite automaton of size proportional to the regular expression, or by a deterministic FA which is potentially ...
9
votes
4answers
2k views

Why are linear bounded automata not as popular as other automata?

In my experience, context-sensitive languages and linear bounded automata are frequently skipped or breezed over in computability theory courses, and are even left out of some notable text books, ...
8
votes
1answer
403 views

What can I say about the Parikh map of a CSL?

Write $\Psi$ as the Parikh map--i.e., $\Psi(w) = \{(\#_\sigma(w))_{\sigma\in \Sigma}\vert w\in L\}$, where $\#_\sigma(w)$ is the number of times $\sigma$ appears in $w$. It's well-known that, for a ...
10
votes
3answers
425 views

Hardness of finding a word of length at most $k$ accepted by a nondeterministic pushdown automaton

Problem statement : Let $M$ be a (potentially nondeterministic) pushdown automaton and let $\cal A$ be its input alphabet. Is there a word $w \in \cal A^*$ s. t. $|w| \leq k$ that is accepted by $M$ ?...
1
vote
0answers
182 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). ...
4
votes
1answer
962 views

The class CFL\cap co-CFL

Is anything nontrivial known about the class $\mathrm{CFL}\cap \mathrm{coCFL}$? In particular, is it known whether $\mathrm{CFL}\cap \mathrm{coCFL} = \mathrm{DCFL}$ (certainly the reverse containment ...
17
votes
3answers
1k views

Properties of Random Directed Graphs with Fixed Out-Degree

I am interested in properties of random directed graphs with fixed out-degree $d$. I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r. ...
3
votes
1answer
383 views

Extension of a partial order to a total of partitions of a weak alternating automaton

My problem is this: given a weak alternating automaton and its partitions, and given a partial order on these partitions, how do we extend the partial order to a total order? The partitions of weak ...
28
votes
2answers
2k views

Conditions for NFA universality

Consider a nondeterministic finite automata $A = (Q, \Sigma, \delta, q_0, F)$, and a function $f(n)$. Additionally we define $\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$. Now lets analyze the ...
11
votes
2answers
552 views

Taxonomy of notable regular expression automata

I'm trying to draw up a taxonomy of algorithms for transforming regular expressions into automata so as to perform some empirical tests of their complexity properties in specific domains. I'm aware ...
0
votes
1answer
1k views

Question about Mapping Reductions (Clarify Example)

I cannot for the life of me wrap my head around these reductions. Specifically, the example I'm wrestling with: ...
26
votes
2answers
2k views

Context Sensitive Grammars and Types

1) What, if any, is the relationship between static typing and formal grammars? 2) In particular, would it be possible for a linear bounded automaton to check whether, say, a C++ or SML program was ...
5
votes
2answers
276 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, ...
8
votes
1answer
454 views

Tool for translating PDAs to CFGs

We know that all push down automata are representable using context-free grammars. Furthermore, there is an algorithm to construct a CFG from any PDA (e.g. Sipser's proof in intro to theory of ...
10
votes
5answers
4k views

Automata Theory / Formal Language Thesis Topic

Hey All, I'm currently trying to find a solid masters thesis topic pertaining to some branch of automata theory or related to formal languages. I'm trying to generate some good ideas for what an ...
11
votes
1answer
608 views

Ehrenfeucht-Fraïssé games (Ajtai-Fagin in fact) for regular languages.

Immerman (Descriptive Complexity, 1999) presents the EF games for existential monadic second order (Ajtai-Fagin games) on page 127. As $\exists$MSO on words is equivalent to regular languages, the ...

1
4 5 6 7
8