# Are HTML and CSS regular languages?

I have a question whether or not CSS and HTML are regular languages.

I believe CSS is a regular language, since it should be possible to create a regular expression to match the structure of CSS.

However, I believe that HTML is not a regular language since you have nested attributes that could be defined recursively.

• – Pål GD Jun 24 '13 at 15:52
• An even simpler question than the HTML is Can regular expressions be used to match nested patterns? The answer is no. To see that it is simpler, simply translate ( to <p> and ) to </p>. – Pål GD Jun 24 '13 at 17:19
• However, then an even easier problem is to see if, let's call it "Linear nested parentheses matching", where the input is "$(^n)^n$", i.e., first an arbitrary amount of opening braces followed by the same number of closing braces. But this is exactly the classical non-regular $\{0^n1^n \mid n \in \omega \}$-language. – Pål GD Jun 24 '13 at 17:23
• The first rule of CS: abstract. @PålGD does this for you. For the rest, we have our reference questions. – Raphael Jun 24 '13 at 18:42
• By the way, if one is not convinced the above example with <p>is allowed, the <em> tag allows for arbitrarily deep nesting. – Pål GD Jun 24 '13 at 19:15

Providing a regular expression or DFA for a language and proceeding to demonstrate that it is correct for the language in question generally constitutes a pretty convincing argument for the regularity of the language. To prove a language is non-regular, you have a few options: the pumping lemma for regular languages is a classic standby, but the Myhill-Nerode theorem is pretty nifty, too (especially since you can use it to prove regularity as well as non-regularity).

Your first job should be to define what constitute valid strings in the languages $HTML$ and $CSS$. Note that most browsers will take anything you call $HTML$ and display something without error; in that sense, anything is valid $HTML$, and the language $\Sigma^*$ is trivially regular. However, I think it's safe to assume that you have something a bit more strict in mind: $HTML$ consists only of those strings that conform to some standard, which probably calls for matched tags. In this case, you should be able to prove that $HTML$ isn't regular, since you can consider the following kinds of strings (whitespace is added only for clarity and could be removed in the real string):

<html>
<body>
<table>
<tr>
<td>
<table>
...
</table>
</td>
</tr>
</table>
</body>
</html>


This language, <html><body> $($ <table><tr><td> $)^n($ </td></tr></table> $)^n$</body></html>, should be enough to get to a proof of non-regularity, provided you accept the above as valid $HTML$, and would say that a missing </table> tag would make the resulting string invalid $HTML$, even though browsers would try to render it anyway.

For $CSS$, first figure out what strings you think are valid, then try to come up with a regular expression or DFA for the set of all $CSS$ strings, or figure out how to define a subset of $CSS$ that requires non-local checks and unbounded memory (counting, matching, nesting, etc.) If you can define such a subset (like we did for $HTML$ above), then you're good to go.

• I wonder: in practice, the nesting depth may be bounded by a constant, due to coding standards resp. best practice. – Raphael Jun 24 '13 at 18:43
• cool, thanks for that answer! I guess I can build a regex, that can parse CSS, because it follows the same structure, isn't nested, and you have a finite amount of keywords to use. Am I right? – 23tux Jun 25 '13 at 16:05
• Note that while the language $\Sigma^*$ is regular, the HTML spec defines how to parse any character stream and that cannot be correctly implemented with a finite state machine (it has a stack of open elements, for a start). – gsnedders Jan 21 '14 at 17:32