Skip to main content
Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Code code:"if (foo != bar)"
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Saves in:saves
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with
Search options not deleted user 5183

formal languages, grammars, automata theory

7 votes
Accepted

What kind of language is needed to recognize an ordered list? [multihead automata, apparently]

It sounds like what you are looking for are multihead automata (in your case, 1-way 2-head deterministic finite automata should suffice). I'm not really an expert on these, but google turns up some in …
Klaus Draeger's user avatar
13 votes
Accepted

Is the Set of all Primitive Words a Prime Language?

The answer is yes. Suppose we have a factorization $Q = A\cdot B$. One easy observation is that $A$ and $B$ must be disjoint (since for $w\in A\cap B$ we get $w^2\in Q$). In particular, only one of …
Klaus Draeger's user avatar
7 votes
Accepted

The number of states of local automata

Since you say that $T_w:=\{\delta(q,w):q\in Q\}$ should have at most one element, I'll assume that you use the version of DFA where $\delta$ can be partial. Then this is a counterexample: $X=\{a,b\}, …
Klaus Draeger's user avatar
25 votes
Accepted

Why is non-determinism (Push-down automata) necessary?

I'm not quite sure which flavour of "why" you are looking for. One reason for the increase in power when allowing nondeterminism can be seen in the following example: Let $L$ be the set of palindrome …
Klaus Draeger's user avatar
11 votes
Accepted

Measurable language which is not $\omega$-regular

A simple class of examples can be found by considering singleton languages $\{w\}$. These are measurable (Let $C_n(w)$ be the set of words agreeing with $w$ up to the $n$-th letter, then $\{w\}$ is th …
Klaus Draeger's user avatar