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.

Improve this question
$\endgroup$
7
  • 8
    $\begingroup$ Classic SO answer. $\endgroup$ Commented Jun 24, 2013 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$ Commented Jun 24, 2013 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$ Commented Jun 24, 2013 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$ Commented Jun 24, 2013 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$ Commented Jun 24, 2013 at 19:15

1 Answer 1

Reset to default
11
$\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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I wonder: in practice, the nesting depth may be bounded by a constant, due to coding standards resp. best practice. $\endgroup$ Commented Jun 24, 2013 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$ Commented Jun 25, 2013 at 16:05
  • 1
    $\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$ Commented Jan 21, 2014 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.