5
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Classic SO answer. $\endgroup$ – Pål GD Jun 24 '13 at 15:52
  • 2
    $\begingroup$ 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>. $\endgroup$ – Pål GD Jun 24 '13 at 17:19
  • 2
    $\begingroup$ 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. $\endgroup$ – Pål GD Jun 24 '13 at 17:23
  • $\begingroup$ The first rule of CS: abstract. @PålGD does this for you. For the rest, we have our reference questions. $\endgroup$ – Raphael Jun 24 '13 at 18:42
  • $\begingroup$ By the way, if one is not convinced the above example with <p>is allowed, the <em> tag allows for arbitrarily deep nesting. $\endgroup$ – Pål GD Jun 24 '13 at 19:15
10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I wonder: in practice, the nesting depth may be bounded by a constant, due to coding standards resp. best practice. $\endgroup$ – Raphael Jun 24 '13 at 18:43
  • $\begingroup$ 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? $\endgroup$ – 23tux Jun 25 '13 at 16:05
  • $\begingroup$ 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). $\endgroup$ – gsnedders Jan 21 '14 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.