C'è uno schema JSON per macchine a stati nel progetto SJOT:
{
"$schema": "http://json-schema.org/draft-04/schema#",
"$ref": "#/definitions/0",
"definitions": {
"0": {
"type": "object",
"properties": {
"a": { "$ref": "#/definitions/1" },
"x": { "type": "boolean" }
},
"additionalProperties": false
},
"<DEF>": {
"type": "object",
"properties": {
"a": { "$ref": "#/definitions/<DEF>+1" },
"b": {
"anyOf": [
{ "$ref": "#/definitions/0" },
{ "$ref": "#/definitions/<DEF>" }
]
}
},
"additionalProperties": false
},
The JSON Schema has N
definitions. The "words" we validate with the schema are defined by the regular expression (a{N}|a(a|b+){0,N-1}b)*x
that describes a sequence of a
and b
ending in x
. The word abbx
is represented by the JSON pointer a/b/b/x
which is {"a":{"b":{"b":{"x":true}}}}
.
Then we add N-1
definitions <DEF>
to the schema enumerated "1", "2", "3", ... "N-1"
where "<DEF>+1"
wraps back to "0"
when <DEF>
is equal to N-1
.
This "NFA"
on a two-letter alphabet has N
states, only one initial and one final state. Its equivalent minimal DFA has 2^N
(2 to the power N) states.
In the worst case, a validator that uses this JSON schema either takes 2^N
time or uses 2^N
memory "cells" to validate the input.
Riferimenti