Given a fixed regular language R, what is the complexity of generating all members of R with length at most $n$? Suppose some reasonable model (RAM with $n$-bit words?) and a write-only output tape. ...
I'm reading Thomas Wilke's survey on the connections between Temporal Logic and finite automata, finite semigroups and first-order logic. In Theorem 6 (by Kamp), the fragment ...
If you ask a question about parsing HTML with regex, you will certainly be referenced to this famous rant. Though there is not a canonical rant for it, I've also been told that regex aren't powerful ...
can you please tell me how can I show that there exists an algorithm that can determine for every regular language L, whether or not |L| ≥ 5
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 ...
Define the following class of "circular" languages over a finite alphabet Sigma. Actually, the name already exists to denote a different thing it seems, used in the field of DNA computing. AFAICT, ...
I was wondering if the JSON spec defined a regular language. It seems simple enough, but I'm not sure how to prove it myself. The reason I ask, is because I was wondering if one could use regular ...