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

<p>For example, consider an array of arrays of arrays:</p>

<pre><code>[ [ [ 1, 2], [2, 3] ] , [ [ 3, 4], [ 4, 5] ] ] 
</code></pre>

<p>Clearly you couldn't parse that with true regular expressions.</p>

CC BY-SA 2.5
2010-12-27T23:36:18.757Z
To obtusely split hairs, the JSON representations of all arrays of arrays of arrays of integers *is* regular.
Charles Stewart
CC BY-SA 2.5
2010-12-28T00:49:29.710Z
Then keep adding "arrays of" recursively until you are happy. ;-)
Marc Hamann
CC BY-SA 2.5
2011-01-31T13:39:57.793Z
Standard JSON is context-free, but most implementations only support unique keys. I moved my unanswered question from stackoverflow to: http://cstheory.stackexchange.com/questions/4668/which-formal-language-class-are-xml-and-json-with-unique-keys
Jakob
CC BY-SA 2.5
2011-01-31T15:18:23.123Z
Note that I said "at least context-free".
Marc Hamann
CC BY-SA 4.0
2019-11-24T23:04:49.867Z
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?
jchook
CC BY-SA 2.5
2010-12-27T19:06:38.677Z
2010-12-27T19:06:38.677Z
Marc Hamann
<p>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.</p>

<p>Hence, JSON is not regular.</p>

CC BY-SA 4.0
2019-11-24T23:08:48.163Z
Curious, what's the superscript/bracket notation used here?
jchook
CC BY-SA 4.0
2019-12-26T23:19:38.857Z
@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.
Nick ODell
CC BY-SA 2.5
2010-12-30T00:36:24.217Z
2010-12-30T00:36:24.217Z
RegexFan
<p>I was wondering if the <a href="http://www.json.org/">JSON</a> spec defined a regular language.  It seems simple enough, but I'm not sure how to prove it myself.</p>

<p>The reason I ask, is because I was wondering if one could use regular expressions to effectively pars JSON.</p>

<p><em>Could someone with enough rep please create the tags</em> <a href="/questions/tagged/json" class="post-tag" title="show questions tagged 'json'" rel="tag">json</a> <em>and</em> <a href="/questions/tagged/regular-language" class="post-tag" title="show questions tagged 'regular-language'" rel="tag">regular-language</a> <em>for me?</em></p>

CC BY-SA 2.5
2010-12-27T20:42:30.333Z
I removed the tag [json] because it does not seem to be worth a tag on TCS SE.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-27T20:46:21.893Z
@Tsuy, sounds good.  Obviously I'm not an avid user of the site, so I'm sure you know better.
jjnguy
CC BY-SA 2.5
2011-01-12T16:58:41.573Z
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.
Xodarap
<fl.formal-languages><regular-expressions><regular-language>
Is JSON a Regular Language?
jjnguy
# Is JSON a Regular Language?

(Asked by: username_0 on 2010-12-27)

I was wondering if the [JSON](http://www.json.org/) 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* [json](/questions/tagged/json "show questions tagged 'json'") *and* [regular-language](/questions/tagged/regular-language "show questions tagged 'regular-language'") *for me?*

**Tags:** fl.formal-languages, regular-expressions, regular-language
> **Comments:**
> **username_1**: I removed the tag [json] because it does not seem to be worth a tag on TCS SE.  
> **username_0**: @Tsuy, sounds good.  Obviously I'm not an avid user of the site, so I'm sure you know better.  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_7 on 2010-12-30. Score: 31 | Accepted answer

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.

> **Comments:**
> **username_6**: Curious, what's the superscript/bracket notation used here?  
> **username_8**: @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.  

---

### Answer by username_3 on 2010-12-27. Score: 32

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.

> **Comments:**
> **username_4**: To obtusely split hairs, the JSON representations of all arrays of arrays of arrays of integers *is* regular.  
> **username_3**: Then keep adding "arrays of" recursively until you are happy. ;-)  
> **username_5**: Standard JSON is context-free, but most implementations only support unique keys. I moved my unanswered question from stackoverflow to: http://cstheory.stackexchange.com/questions/4668/which-formal-language-class-are-xml-and-json-with-unique-keys  
> **username_3**: Note that I said "at least context-free".  
> **username_6**: 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?  

---

