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 expressions to effectively pars JSON.

Could someone with enough rep please create the tags and for me?

  • 6
    $\begingroup$ I removed the tag [json] because it does not seem to be worth a tag on TCS SE. $\endgroup$ – Tsuyoshi Ito Dec 27 '10 at 20:42
  • $\begingroup$ @Tsuy, sounds good. Obviously I'm not an avid user of the site, so I'm sure you know better. $\endgroup$ – jjnguy Dec 27 '10 at 20:46
  • 1
    $\begingroup$ Remember that regex implementations frequently match more than just regular languages. E.g. you can use lookaheads in most implementations, which will accept $a^nb^n$ correctly, solving the $[^nx]^n$ problem others mentioned below. $\endgroup$ – Xodarap Jan 12 '11 at 16:58

Since $a^n b^n$ is not a regular language, neither is JSON, since $[^n 5 ]^n$ is valid input for any $n$. Likewise, your regular expression parser would have to properly reject any input $[^m 4 ]^n$ where $m \ne n$ which you cannot do with regular expressions.

Hence, JSON is not regular.

  • $\begingroup$ Curious, what's the superscript/bracket notation used here? $\endgroup$ – jchook Nov 24 '19 at 23:08
  • 1
    $\begingroup$ @jchook The superscript notation means 'repeated.' So $a^n$ would be $a$ repeated $n$ times. Similarly, the notation $[^n$ means $[$ repeated $n$ times. The brackets have no special meaning. A regular language cannot 'count' how many brackets are on each side, so they cannot tell if both sides have the same number of brackets. $\endgroup$ – Nick ODell Dec 26 '19 at 23:19

No, it's not regular. Since it allows arbitrary embedding of balanced delimiters, it must be at least context-free.

For example, consider an array of arrays of arrays:

[ [ [ 1, 2], [2, 3] ] , [ [ 3, 4], [ 4, 5] ] ] 

Clearly you couldn't parse that with true regular expressions.

  • 8
    $\begingroup$ To obtusely split hairs, the JSON representations of all arrays of arrays of arrays of integers is regular. $\endgroup$ – Charles Stewart Dec 27 '10 at 23:36
  • 16
    $\begingroup$ Then keep adding "arrays of" recursively until you are happy. ;-) $\endgroup$ – Marc Hamann Dec 28 '10 at 0:49
  • 1
    $\begingroup$ Standard JSON is context-free, but most implementations only support unique keys. I moved my unanswered question from stackoverflow to: cstheory.stackexchange.com/questions/4668/… $\endgroup$ – Jakob Jan 31 '11 at 13:39
  • $\begingroup$ Note that I said "at least context-free". $\endgroup$ – Marc Hamann Jan 31 '11 at 15:18
  • $\begingroup$ Expanding on @CharlesStewart's comment, does this mean that "JSON with a strict max depth IS a regular language"? Or do other features of JSON prevent this? $\endgroup$ – jchook Nov 24 '19 at 23:04

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.