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

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

• I removed the tag [json] because it does not seem to be worth a tag on TCS SE. Dec 27, 2010 at 20:42
• @Tsuy, sounds good. Obviously I'm not an avid user of the site, so I'm sure you know better. Dec 27, 2010 at 20:46
• 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. Jan 12, 2011 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.

• Curious, what's the superscript/bracket notation used here? Nov 24, 2019 at 23:08
• @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. Dec 26, 2019 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.

• To obtusely split hairs, the JSON representations of all arrays of arrays of arrays of integers is regular. Dec 27, 2010 at 23:36
• Then keep adding "arrays of" recursively until you are happy. ;-) Dec 28, 2010 at 0:49
• 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/… Jan 31, 2011 at 13:39
• Note that I said "at least context-free". Jan 31, 2011 at 15:18
• 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? Nov 24, 2019 at 23:04