-4
votes
1answer
29 views

Is there any way to complement a regular expression? [on hold]

I've been studying Finite Automata for a while now and I know a DFA is closed under complement whereas NFA is not. I've just started with Regular expressions and was solving problems where I got ...
0
votes
1answer
57 views

Finding containing sets, within sets of sets

Let $s = \{\sigma_1, \sigma_2 \ldots \sigma_n\}$, where $\sigma_i \in \Sigma$, denote a set of alphabet characters. And $s \in S$ where $S$ denotes a set of sets. Given a new set $s' = \{\sigma'_1, ...
7
votes
3answers
252 views

Algorithm for ranking members of a regular language?

A little while back, I was reading a paper that mentioned a method for computing an integer 'rank' for a particular string $s \in L$ where $L$ is some regular language. This rank uniquely determines ...
7
votes
1answer
188 views

Regular expressions of families of regular expressions

I was reading about the Star Height Problem and noticed that Eggan's family of regular expressions follows a simple pattern which can be described by a regular expression. My question is: are there ...
19
votes
1answer
679 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
315 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 ...
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 ...
8
votes
2answers
2k 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 ...