Questions about the formal languages that can be described by regular expressions (in the sense of Kleene), or, equivalently, the languages that can be accepted by finite automata.

learn more… | top users | synonyms

-5
votes
1answer
2k views

Proof that DFA that accepts string has NFA that accepts reversal of string

I have seen descriptions for an algorithm that can take a regular deterministic finite automata and create a non-deterministic finite automata that is guaranteed to generate the reverse of string ...
27
votes
0answers
513 views

Eilenberg's rational hierarchy of nonrational automata & languages — where is it now?

In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational ...
16
votes
3answers
524 views

What is the minimal extension of FO that captures the class of regular languages?

Context: relations between logic and automata Büchi's Theorem states that Monadic Second Order logic over strings (MSO) captures the class of regular languages. The proof actually shows that ...
2
votes
1answer
250 views

FSMs with finite memory

Consider an FSM and a finite set of variables. The FSM has the special property that each state contains a set of commands, with each command taking the form of "variable = expr(variable, ...)" e.g., ...
24
votes
1answer
887 views

Why are regular languages called “regular”?

Why are regular languages (and from that regular expressions) called "regular"? There is lot of regularity also in context-free languages other types of languages. I suppose that, in the beginning, ...
4
votes
2answers
344 views

Matching regular expressions using regular expressions

Is it possible to create a regular expression that matches regular expressions in any given notation? Or, in other words, does there exist a unambiguous and full notation for regular expressions that ...
6
votes
1answer
379 views

On the relation for the Myhill-Nerode theorem/syntactic monoid of a language

In order to characterize regular languages one finds the following definition useful: Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\equiv_L$-related, and ...
18
votes
2answers
1k views

Counting words accepted by a regular grammar

Given a regular language (NFA, DFA, grammar, or regex), how can the number of accepting words in a given language be counted? Both "with exactly n letters" and "with at most n letters" are of ...
6
votes
3answers
576 views

Complexity lower bound for regular languages

Suppose I have a regular language $L$, and I would like to lower-bound the complexity of deciding membership in $L$. Suppose I know that the minimal DFA for $L$ has $N$ states. I would like to claim ...
8
votes
0answers
420 views

Number of equivalence classes in regular languages as a function of DFA size

This question is related to a recent question by Janoma. Background In constraint programming, a regular global constraint $c$ over a domain $D$ is a pair $(s, M)$ with $s$ a tuple of variables ...
16
votes
1answer
1k views

What is the number of languages accepted by a DFA of size $n$?

The question is simple and direct: For a fixed $n$, how many (different) languages are accepted by a DFA of size $n$ (i.e. $n$ states)? I will formally state this: Define a DFA as ...
6
votes
2answers
275 views

Generating all instances of a regular language up to a certain length

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. ...
6
votes
1answer
253 views

What is an unambiguous language in the sense of Schützenberger?

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 ...
4
votes
6answers
1k views

What are regular expressions good for?

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 ...
0
votes
0answers
224 views

algorithm that can determine for every regular language L [closed]

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
17
votes
5answers
897 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 ...
18
votes
5answers
1k views

A special class of languages: “circular” languages. Is it known?

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, ...
9
votes
2answers
3k views

Is JSON a Regular Language?

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 ...