Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
6  
I removed the tag [json] because it does not seem to be worth a tag on TCS SE. –  Tsuyoshi Ito Dec 27 '10 at 20:42
    
@Tsuy, sounds good. Obviously I'm not an avid user of the site, so I'm sure you know better. –  jjnguy Dec 27 '10 at 20:46
1  
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 Jan 12 '11 at 16:58
    
@Xodarap, thanks for the additional info. –  jjnguy Jan 12 '11 at 18:33

2 Answers 2

up vote 17 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
5  
To obtusely split hairs, the JSON representations of all arrays of arrays of arrays of integers is regular. –  Charles Stewart Dec 27 '10 at 23:36
12  
Then keep adding "arrays of" recursively until you are happy. ;-) –  Marc Hamann Dec 28 '10 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/… –  Jakob Jan 31 '11 at 13:39
    
Note that I said "at least context-free". –  Marc Hamann Jan 31 '11 at 15:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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