Parsing context-free grammar
Statement
Goal
Difficulty: HardTopic: Context-free grammars, CYK algorithm, dynamic programming
Given the context-free grammar and a set of words, your task is to decide which words belong to the language defined by that grammar.
The grammar is presented in Chomsky normal form, without epsilon-rules. Non-terminal symbols are always uppercase letters, terminal symbols are always lowercase letters.
Input
Line 1: the number N of rules in the grammar
Line 2: the character START indicating the start symbol
Next N lines: rules of the grammar
Next line: the number T of testcases
Next T lines: words to parse
Line 2: the character START indicating the start symbol
Next N lines: rules of the grammar
Next line: the number T of testcases
Next T lines: words to parse
Output
T lines containing true if word can be successfully parsed by the grammar, false otherwise.
Constraints
0 < number of terminal symbols < 25
0 < number of nonterminal symbols < 25
0 < N < 100
0 < T < 100
0 < length of word < 100
0 < number of nonterminal symbols < 25
0 < N < 100
0 < T < 100
0 < length of word < 100
Example
Input
6 S S -> SS S -> OT T -> SC S -> OC O -> a C -> b 10 ab ba abba ababab aaabbb abaabb a aaabababbb aababababbb aaabababbabb
Output
true false false true true true false true false true
Tags
State machine, Dynamic programming
Difficulty
Hard
Test cases
Well-formed brackets Test
Input
6
S
S -> SS
S -> OT
T -> SC
S -> OC
O -> a
C -> b
10
ab
ba
abba
ababab
aaabbb
abaabb
a
aaabababbb
aababababbb
aaabababbabb
Output
true
false
false
true
true
true
false
true
false
true
Well-formed 2 types of brackets Validator
Input
11
S
S -> SS
S -> OT
T -> SC
S -> OC
O -> a
C -> b
S -> XY
Y -> SZ
S -> XZ
X -> x
Z -> z
10
xz
za
abxz
abxzxz
axabzb
abaxzb
z
axabxzabzb
xxbazababzb
xaxzabxzbabz
Output
true
false
true
true
true
true
false
true
false
true
Well-formed brackets - ambiguous Test
Input
15
S
S -> SS
X -> XS
X -> SY
S -> OT
Y -> OT
T -> SC
T -> YC
S -> OC
S -> OD
X -> OE
O -> a
Q -> a
C -> b
D -> b
E -> b
10
ab
ba
abba
ababab
aaabbb
abaabb
a
aaabababbb
aababababbb
aaabababbabb
Output
true
false
false
true
true
true
false
true
false
true
Well-formed 2 types of brackets - ambiguous Validator
Input
22
S
S -> SS
W -> WS
W -> SY
S -> OT
Y -> OT
T -> SC
T -> YC
S -> OC
S -> OD
W -> OE
O -> a
Q -> a
C -> b
D -> b
E -> b
S -> XY
Y -> SZ
S -> XZ
W -> XR
X -> x
Z -> z
R -> z
10
xz
za
abxz
abxzxz
axabzb
abaxzb
z
axabxzabzb
xxbazababzb
xaxzabxzbabz
Output
true
false
true
true
true
true
false
true
false
true
Small grammar, many short tests Test
Input
20
B
F -> a
F -> b
C -> c
F -> d
F -> e
A -> DF
E -> BE
D -> BD
B -> EF
D -> CF
B -> CE
A -> EA
D -> CC
E -> EF
A -> EA
C -> FE
F -> BF
E -> FD
B -> CA
E -> EE
60
eeeccbcecabecbccacaacaceacda
ccacdddbaecbedeaaecdc
eabdcbbeaaddddadbddbaad
dccddadddcacddbdaebc
eddddaaeeabdeeabdbeebcae
aaceacaceaacdbaacaacedbdccecc
aacbadcdbebabbecdebdd
aeabeeccdcedceccdedaaebbdbb
bebcbebeaccbdedecacee
abdabcaabbbdeadbbeeaeacdade
cbbaddcabcbbeeedeabacddad
aeebcdadedaebdebebbaaeaeb
bcaaaaccddcdaadaecabec
edbcbdddcacebcaeeddd
dcdebbeeccbebbdbadccdbbddabb
bbbbababdadbddbbdbdbdddde
bdebbbaeabddceeddecaac
bbdbdecacdceebeadbbeb
aaacbbecedbdeebccbcbcebbae
bebdedbaaaaedeabadeddace
bebededaaabecedccbdc
cecdbececdcdeddbeceeaeaae
eaadcdcaaaecddcbaaacedc
acbadbbaabeaeccdcaedaba
baacedeededaccacecccebaaeaebbc
dbebebbbbebebbeebaedcdd
addcccacdbacdabcbbdbeaaec
bbbbeedcbcbdacdaacdbdbdbbdedec
ebaeceeeadbbbadedaac
cbdaeaadaeaaddddaecaaee
deddbbbcbbcdbeecdebdbc
ecdceaebcaeaccbceeaceead
ddeeabeeaabeebeeceacbeb
edbeddcabececbdaecabaad
eacbecbccacaedabadcbebebab
adbcdcdcaacedbbceeda
dcbababebaeeeaccdedcaaaeeab
bbbbdeadabaaaaebabad
ecbaecdcbbeeeceabbcb
ccebdbddcdcbaecaddbeceddcbecc
badaabcaeeaeadbababbda
baabedaebdeaabeecccb
acaccbecceeddbbbbdbdeccacebbba
edecedcecabcbdcabddbedbdac
abbcaaeaabeebcbdecedcabac
aaecdbabbdebddabbeedc
adeadacebeccebebedeaacd
acebcebacedcaaccaedbec
eabeccbeaececdbbccadbccd
babeceeabcabcebbbcbaebeeaddbb
baeabddbbeabacabbcaa
baabbaeceadbddabdbdaedcc
abddcbadaecdcadccbccdaadeeabc
ccddeadadeeaedadeeacdd
acdcbebdaebeaabcbbdc
cdcccdcaaeeaeaaadabeeaac
edaddabddbaebacecedeec
dedaeacddecacceaceeecebdcccda
badeededeaeacecbcddebcaeddc
eacbeccaddaedaaeabdaa
Output
true
true
false
false
false
true
true
true
true
true
true
false
true
true
true
false
false
true
true
false
false
true
true
true
false
false
false
false
false
false
false
true
false
true
true
true
true
false
true
true
false
false
true
false
false
false
true
false
true
true
false
false
true
false
false
false
false
true
false
true
Small grammar, many short tests II Validator
Input
21
C
E -> a
A -> b
E -> c
F -> d
B -> e
D -> DD
C -> EE
C -> AA
A -> BC
A -> EA
C -> FB
D -> AE
E -> AF
B -> FA
E -> BB
D -> CC
B -> CA
D -> FF
B -> FF
A -> EF
B -> AF
60
cdecabbeccdcbbeddbbbbceed
acbabecdeeddecbaaacc
abeaceebcecbdcadaecbaeeae
dbeecbccbdcaeacabdadeebbabb
beacbddaeeddccaaebbd
acbbeaeecccbbececbacbaccac
ecdabcecbbdaceeebbdabdbdddc
dbaebbbbdbddbdeadacbebccd
ecbaacddbbebcbeebeaabcadec
ebcbdaaeaebcbeeadbcbecebeaea
cebecdceabccedcceabccdbedaec
edeaeeaaabdddabeedad
ddcabcdcbdaaaebaaaedccde
adddecabeddbcabacabbab
cbedceacbdcdecadebddcee
cbaccecdeeabbedbecba
decabbeeedddeaedbebcadaedaeae
dcbdedcdeecdbbaabdaadabddb
deacdbccabeabdabbbabdbad
cebcecbddceaabddcbecebececeac
bbabcaadaabdeeeeccaeaaabe
bccaaaebcbeecbeaeaaaedd
adbbddaaedcdccdbecdad
ceaaabbcbecdcedbdccebdbdba
eaebaebedabbcdcabcdc
bbcbcdadcbbebbdebabdbcbae
dedbebdbbabcbbcbdbaecabbebc
ccbcdababbeabedcbebcbbadbdc
caceaeeeeaaeebaebcbece
cceceadcadcddaebaadcebeabeec
aededeadaaebecaaceaebcec
cddaacecdabdbaabcdbbddbeceeb
dbadbdbbbdceceaebbebdecee
eaaddaeaebaeacbacdabce
aabbbcaecdbccacebbbecedebc
bdcbddbcabbcaaddccdcbdbc
ccadeacdeeddaaadbeadeabcb
bceaceeaaccecbedcacab
cbdedeabcaeedaaaebeda
aacaedebdbecbdbeadcdccb
bcbaaabebcccabadcadaceaeaebcae
beeadadecaebabaaecdbad
eedeeecedbbbbedcaecbeeae
ecdcbceaeecdaeaddbaeecdab
dbcbdbeaaddbccccdeebddeaace
cecebaecbededebccaeec
bcdcadbeaadcbdcacbddabdd
dbebcebeddcbcdbacaaaebaa
ccaebeabeccacaebecba
bedddddccdcdeccbdcaeacdded
dcebaeddcbceacdddcabaaacebedab
cceeeacbaececceadcbbb
dceaecdcedadcdebeccaee
aabbcacceecebcdeaacedbc
bedceddadeaedccaadbceea
caececcaeeeebbdaebcec
aadeadaecdadbdacaceb
ebaaccdaeecbbeadccebc
ddacdbedeedaccabceadbda
baadebadbbacdbedadbdade
Output
true
false
false
true
true
false
true
true
true
false
false
true
false
true
true
false
false
true
true
false
true
false
true
true
true
false
true
true
false
false
false
true
false
false
true
true
true
false
false
true
false
true
false
true
true
false
true
false
false
true
true
false
false
false
false
false
false
false
true
true
Large grammar, many medium tests Test
Input
50
L
J -> a
J -> b
I -> c
G -> d
H -> e
D -> f
H -> g
G -> h
B -> i
B -> j
K -> k
L -> l
A -> m
F -> n
G -> o
E -> BA
C -> AG
I -> FD
K -> GJ
B -> KD
I -> BE
J -> KH
C -> DB
C -> CF
D -> JA
A -> DL
B -> JH
G -> HF
C -> JH
F -> GK
L -> DF
E -> CB
A -> ID
B -> JH
K -> KC
E -> JH
L -> AB
G -> IA
B -> BB
K -> KF
A -> BC
K -> BH
G -> EF
I -> CH
A -> BE
D -> AL
K -> AE
L -> JE
D -> LH
D -> GD
80
fboimhogffkcocclejjmhhkcjchmjioigfbgkojklcbjglbobgaefijejieecaamgc
kbgcfhinofkgekaefoadf
enajibeebbgigehmbgmfjnjfmigamimgemmdefkeekeeaejkfifmnk
heihalfnlklecefffjjohgnfmacgkgnblkggmcfabkibmaaljicidghggjinfa
ikgjcfonagmignmogaeefmjimfg
ammgdlbdgdkbghnahhmfhjncgamchnfifghmgdneljhdadd
gdfedkbnbfabegcdjbdjeloegnaicenmegnndheg
kddnjmliciaoejigmigloghaghijnkkjajjfeedjnfhkdfd
ifgeghcjhbbomhgcmcngdjbbiajbbabaagebjdonlhhmalhaejommnncakagagjkgdg
dkgbmkggjkggbemogkgimgokifjhnbgfaej
keeemkngebgjebjkggkkggnfm
gfnmlnhfkfjkdledmoecfoidhkoambkhfmdcfhjddnagfledbconkbcmnjog
gkkekfnaldgbkjilghkhjghfhieinobfiakkcald
cmkecflamlbeieokejagndfkgnhfmlmbemimgeekgem
kkhamdamgoiheibilhencgnncmmjhjokgmoddhjh
dfdjjagaee
obnfdbmdiomojmbklahbbkonhkgoichmbhgifjfako
jaagkanlebkbgiadlonbibglckkdnbnfnhdiaebbjdnfggbadfidbhoaomhhdbigfjlo
kgcmmdnjnjmnfamenjikeekfaglekmhkfhkmagkeekegdkflkgfjkf
ceockboiofbifnifbobkhemmijgijkflafemfdmm
dbldamedmceblljhbnekoheljmgkjcdofoefaheodhjghlngmkmcahofof
jhgbdhjmoddjlomfgeecnjdandcklhimkbkjgiegdjlkljmmdleob
iegkfkfnleaeknfkgg
kcjdbakohjkkaalbhncaoobojconmgmihbikmionajjohnoildbjfonoolm
flkegdkngdhkfmflehknlgfkkgeejcfobge
mohgiaonaikccclkicognbmaffjkkgkhfgmhkcgkmmodfloaoloinolojjodjlka
dceheidjjabiodocejlajmiafafoaecdjlibmhfbnbbgamjfnafeaofelgnmlkgmgfm
jkeeeggaeokeegehf
baajlgibklhhkjkggeiklinljcabkgjaokchiijdejabc
mij
kgmjeknegnjjege
lojijdhaklblmeneologogkocmajmhmeefffmjkdjdnahjalcocomhkikdkcc
jjjeajiiikiiecicnffniilfnleegiglfmckbnfgdhfdedbd
okgmhnjnkgffaehkcjaennicflekfggg
hgblngbfenhhhlakjmghddmgbkjojbjfonfldeeklcdobbdn
cnihgdncgnmnaejofkhakmhdigdadiknknnldkmcojmljoldohkbjhij
kegnkggomjifigaikeemem
kejkeem
ehemdcmfefcngkbkmfbnhbmfammiigflblnmnliecnkjndmklijdnfefbankmajlngi
naifjnfkggngmlfkegjefbgokk
mogndaejmhkagokenffjnkgg
mogmamhilennfjflbeggmkggigggicfdnikbgee
dknmmjmmjkdknkgm
cfbgfagijagikgeijiclgaejgnmimaedbnge
oogjadaaaaflidhjbfombafgkblfcjacnkkkkabnjomlmlmjhc
hjblbeaglaledbnlfaolodnabjabnebiabiceabcfdlaohgjankgfdg
fcibmimkgejmd
mjcaljcgjdgjmodndgohncigjcaimkhbheioemfkifdgdcijnffojikinlogdch
echckoobknomlhacomifmfblekcnchnlddlhcmgkhimga
kdacoaklgmgnjdicibkbijfhlhhoenelkohagbknhbohhecadlcgkhddofjodekedin
ffccmeaogcccfgckejmhfnfcafmajfhmliiifooofdghjdkcckjoecdaiocff
kgkeg
iehfjnembgieegeg
kamegkggkaehkfclekggfnegg
kcfhgkjhaekdajebdacecdeoeneiknjfghhhggikfbjolkomkffilmc
hcielhdedlcgbflekldkmeldgdcdejkddeljmkibcikilddbmoa
mfbbofllfdciimgkfgmibaglagfbigfgdeddibbehlbnc
ignhkebegfiieefmign
khkfinagokklemaehcfjmfkeghoklejemkegmggiggg
efekbljonmnoafdbnmlehakcehehldjkadnojgdlnbnmjmjhofledkcggfhajmadkga
ckefkggiekge
aecikcmcbjklfbdhlnldajhoajcjjohloejmjnfgiba
ffdkflfjjndknij
ilingjjkkannkhmbblgndfafnonmjglahhdignigkbbnhiecbmbielbbi
ehkkggbggge
bhaebgkeeekeoigfjiifkgeaebikfkgg
hkdffojeeojfagjjekge
affdklaaeningibemdke
ejcjbijaoemjidlmjalnfabdhdkfhamnnfidnlnagemegbkmhfkgcbhbedgljjlbfflhbh
keegemljnfjfijkkfjmdijihf
ojldhnnndifckgnfbdaibecniggnmgghcgenlblcfhgalkdkihaklbbkobiojnmakokhcl
bnfllfcmj
kokaebenemmjmggbeembefkngmdjm
kgenkegeeohkgoign
eaenkdbfmaglmaoalinjheblonlfinhgiflclaodjihibbkhmbhgbgkgk
abgoknjjgcmkhk
kgkhkfikfhaamkemjaebgiimdghkkmhokigmfidkngm
jlgjijjijggjbeni
fdcmhmblcnmfinellgcjifdolaoiceaejmedjljbebeci
kcedfleanmmgioonbbfieihkigoodjeecjlachjhnohjii
Output
false
true
true
false
true
false
false
false
false
true
true
false
false
true
false
true
false
false
true
false
false
false
true
false
true
false
false
true
false
true
true
false
false
true
false
false
true
true
false
true
true
true
true
true
false
false
true
false
false
false
false
true
true
true
false
false
false
true
true
false
true
false
true
false
true
true
true
true
false
true
false
true
true
true
false
true
true
true
false
false
Large grammar, many medium tests II Validator
Input
52
H
J -> a
I -> b
F -> c
F -> d
E -> e
F -> f
L -> g
K -> h
D -> i
J -> j
B -> k
E -> l
I -> m
F -> n
E -> o
G -> p
C -> GD
H -> DA
A -> FD
A -> LB
H -> FK
B -> BA
B -> LI
A -> KA
F -> HG
H -> FK
H -> FF
F -> KA
J -> BG
I -> JL
B -> KI
J -> DB
K -> JI
D -> BK
K -> AA
E -> FH
F -> AI
C -> FE
F -> AD
B -> FG
C -> KG
K -> DK
F -> AL
L -> EI
B -> KJ
J -> EH
B -> II
I -> BA
I -> CD
K -> JB
F -> LK
K -> KF
80
mkgnkgnnlfgdennpnndbkfdeohbefjllhjjakkgaggn
jbkpnbeibjmkinpeekobpbdmidfikbeegagchihjaolpgpgabm
fffaganpkhojghlmkemfgkmlkhmhhhgkighmgih
fihigkpidedhkpbknkhphjljgihgkdkcidi
blkaaknlnlaehgiegmckcgjlfflaikjjphchdgfhimegaeegndjhp
hikpknicgihiikdihgkbmmgbmmekhcikhhdihcnpkhfihjhdikhpfdfmbhemkk
fffmkkhkihfkb
iijcppcciglnhpbjbkcajompepghicojfpdccinfinggnnddfndgfbleh
khkafncbikkhhgkbdkhfcdgkgchgkphahhhnihpinjbpfmhaomgblbklihdih
chcdpkomconfdjlolakfpmndlphfaddlpgkppfodngcckgdiompnjkgfaddfcl
nidpannfkibcijoclmoehmpjlncabdkmagfcmngphehnlnmcpokl
jieickgedkdmbcmjilejokbfngajecpmofjemlbmlchkaiokipfiojgoddkomachph
hhhdaijndfpeldfjfncfcnhjdpadmcmdmmjacclbekekebfia
jhghfafbimbcpnligmkfodhcajhpffnlkbfdcplmeglb
nicimagamgkcfdbkghmdfpikajggmm
khihhpkhaoblmgmikghanihgmmbkjkckhikfigknkhpk
hkppbgkjmnigchhcideiffpghpkhicipgkepiiphanfhcigckhgjkigkhgknkjmicipnkhhmfp
fkhikkgkkpmpijjggjemhphgkgcpimmghhmlfhkhhlmk
pgebkdkmjpeilboiccdiciglmoaamamemniihnnehggnefmnhfmpjabceolhfmeg
kmhddejemplhlbmfecopepidlpgjjnkljngkllbgdjgikfdnlagknecbincfhaoihfdifb
klojhbbljlganbdppbmobbmikbogijhalclhgjgmdfjjnlilok
gmmmdolmolpngddbekkeckcdnakgodhfhapbnpllbpgenhgpkfeo
clmmhgdemdgjgnchcjhajmondchfkbpfajnmpgncjme
kjebpiiihgkhihobmb
oihcpijmkdikiicigkf
kjobmhciihgkbkgpiimkhhhnkjkgkgkiigphhgkgfphcicibdfjdicimficidlikhgkgkpip
foepfnkghonefdafjhfnfdjjgaejkdoepjemndbdbl
cbmhnifnkffhhkhhcifiaobbkhmpkeaghhgkhfihhgkmkhcigig
gblfdjcdfmgokpbkjeemopcedobdbgcfpibaimbfmdjhokfgf
olddjdcmhipeojofbpoppimgbjeokhhibldhakgicmchfcbhmdccjapjlofpiagl
libmajncdkimdcblmbhmmdhkgolmbiafkabcioklknefmekopkjfdeigfaahmieopfjoc
fohpgkiphhjkhhpiikhhhdibfppg
bbbeaaadhnfkaljkocaicopkhifpnmkaamcjjfmfkeglmfma
oobpdefnmhhnfpdcafdaghlhbghifekcaaiahmifnccaglehlflglompelfjcd
hpinckhdikamikpkhkhobjjglhhcimigkbihikk
cblkpllmfgaglfhfnkgmokjemolpaebakjpcmmgdead
agaginfppfgkghfiglcphhomdicihniphbfpm
gihgabgkidciciebhdokgkmkgkgkgk
nkhfininihpihakpjggkdkhggmihpimhkikkhomajgikhjhcigpikhgkkhhhcii
baghgkhcihgkhgkdjknifchkhhgkhhhnihdimmniebhdhkhomkkhhbabb
ojcfjfhdikopbeknndldphjilnaacfcmheldkmoaepppbjbkdll
oipohcmfdpohgmgibloemfmhfoemiocjdolboeedagejkbh
kamgkhdikhkmlkfiklkhhhfijmihniiiddaghndkkpkkh
mmmhcnfbkgkdigkdphfihfidikhebkagmfipiiphfpdphihhgkgkclmiihpkhidphgkip
dojccokbmkmbfdmlnhiipnopbdekebcjmiamlhgbainhohpgeljnkfblikllof
oaomkbnhihnipnihdipknkhblbkjbdibicicihmdgkpikakhdikhkpdphdkpmahhfigkp
igkiiph
ikkppiihmhihcgk
micbikmpafdcdcbkimngolpgkiemgnbplgeebmobnbnnhpbdjglnne
dihndibip
hhjhgnicichmbjgpiidnphdidihgkhgkihihhghncbjgpii
lpigmihghjpebpnphchpipgpii
ckhfihgkmhaakbeknimmhdkhcffidihacihhgkmkkhiakjchhdiidjkcph
ilmkhhgkomdeijmjhpkhlahdiidhbhbnnghhpinfpijkfiiamjfncikcchcei
ficapaahhidijbaaphpcamhilccnggkmgpmehgpbbnfkleklilgpfhfjlimcfkonfhp
odiapolohohhhinbopekbaaeldfccpkaniakjfnknocgelghpfoipedbo
kbkfdohmgiiobnhbapjdilnlipidomdldgfbkckebkfabchjhogmpmcjkddpoidlchbpf
afnhoknlbioeoldppfhjphhmcloejfjeklpddcddhdooocjepppmpcmdaojfgdfj
khdkkpmmigghpihphkphk
lmfmbdafbklbmahfpcebheafpolbhbgclponbgieihmblgfec
gknkhihnkhiichoigkhbhjihhfipdhbk
fkiomekljhfdnjfghdjhafghknhjmlefcdnfmiclhl
fhlhmgkdpopiikhckhenffhkhkhkhci
aionfpijafiddfneaimdleeknacchhpmimnggiabpnaaihcfhalnji
gakgkdphdippikhbbhdfakomk
lhimffefipokmpecbdifaaoinnieeplnlaccakpmhnpknadfaanekcalfd
hjbjkhkfmfelfiemabadkbhnejiecfmfmleklhlpdkdljgdijhbgjelnbnnbml
jkcddecfkfgkdihhgkbhgkhhcjbppi
ffeppehdeknkkanedpcggebhkopbgkognhhbjnnjlkk
hihadihjghkhhnigibnemhjkiobhfimnbhpiphanimkpmdi
khgmkhejgkhhnhnikhicibkkpfekabhkgkhmhhhgkgkgkbhhgkh
pkfepbgfoghenceiaahemklcdhclnabafbkhepfpdpdccfoppihdfobji
dphkgklkgknifhdibegkkhnkgkgkomkkhkhodhfghdinpkhijlhpkjbfokhcihgkchbchegkmhebk
iefhlfnljpcpagdmbbhioimjagnefplbocdlonllfbeohnibedmpebhgpomeagakabopbb
kihkhkhhjaomdilmkhhigkcijegbhccicpihnkhhgk
odhlnlmglgknigllgkdfmoioalbbeifefhcameakiophblglpjfjoegphhgpnhbckc
fpfppbdheikgfdhmhbhghkhkfi
kpgbgkbampibikmigakkfihp
ipmicfmhpigjngfaileekfbldikkmhnbfpkbiikhlfhmhdlepnffinnbjbjnphbplekpje
lhgopokfbehnaoljgekinkllfaelacnidpidojjoikpmlncpbpjjg
Output
false
false
true
true
false
true
true
false
true
false
false
false
false
false
true
true
true
true
false
false
false
false
false
true
true
true
false
true
false
false
false
true
false
false
true
false
true
true
true
true
false
false
true
true
false
true
true
true
false
true
true
true
true
true
false
false
false
false
true
false
true
false
true
false
true
false
false
true
false
true
true
false
true
false
true
false
true
true
false
false
Large grammar, medium number of large tests Test
Input
70
X
L -> a
W -> b
U -> c
B -> d
D -> e
Q -> f
E -> g
T -> h
B -> i
J -> j
V -> k
S -> l
C -> m
J -> n
R -> o
N -> p
N -> q
O -> r
J -> s
J -> t
K -> HV
A -> HA
M -> CN
G -> GQ
H -> NL
P -> PC
X -> XV
F -> AL
I -> KS
M -> WV
V -> VV
I -> PS
V -> HU
F -> NP
H -> NW
G -> OB
J -> UC
B -> JI
C -> JT
B -> GD
K -> CB
A -> PQ
A -> TF
T -> QR
C -> WE
A -> SN
D -> TW
L -> QQ
S -> VL
H -> UP
N -> HX
I -> BG
P -> EF
E -> IG
Q -> NX
I -> VR
K -> BW
C -> LB
E -> SP
M -> CW
V -> AC
K -> SN
P -> SS
B -> ST
J -> NA
U -> XX
X -> MR
U -> BB
U -> KC
C -> NH
40
gisojlafbdssgngdscmcfjqsaornbmetendqnkfbccersqdlqmkbtqitietkqqkrdoqjilbjjepeibtljgoqqhlseodibeja
tpffknhllmmqobbkobcafoqakbgaddrikkakkabkcgpgpahpgqllmmackkpbcokmboobo
bkorqgpgqgllfacllmmqbbkookqbmbokpapagcgqllhglqafaafmkacmpollqbkkkkffkffqmqomabokk
nqabgqobkoobo
lfcekflccricsgdjoqifjabpadrncdfmtennibkhmbmofjhldkijoqngqfhkeqdssbtfmparsjjbeomcidmbhllqmhk
riidgqsjqkqblrprhfgadbfjkseqejsmhiknjbmlnkndjjkdkdofhqrbfimqajdrm
jpffbkokpbkokkkkcllhhqgpllabgkocllbkocgglqafackkalmmpoobo
kafqraaihbhbgqsneejjlgjommsfqdiqimaltpllgqtceejnhqgeprbkghdnctdjarbogekommfmocfnksamnpmfnba
bkcmpmbokordfemllsjhimllmbombokojhpobgpopamqoaqqaqabkoomboglqbbqblpmoabo
mqo
bgqo
mqqbkopbqfffolcgqllmmqokatqbkoopffcfmbobbkkkoo
smjcnsgfpcfqptkiisbjmlhhiqcirrdpqtdonahfftfsprrothfgtmglkadabhhbapdbpekc
ppbbkkopacqfqampokkkkkmbokllqbpahllmmfamonpmbookfcgpbmbolgfoqllahllfaammbompoaiqoabo
mcpkkhiibqgisjpnnsppqeamdokcoanskeaofjspfnoojehtblkb
ecffambjqplglkjlgnteppjpfliilrgrafcqmfsftnnlrjncpcrdrbjfr
ggortegoqgfqfnsjepesjaqpnooolsnbekhshmakanibctbgmqmdnjpbmaeoldrsagompdnchqfsprprnmamrltfbbslkgchlke
dgfplpkhfphafodkpipopbrcdeafrjrkbgnfkbsrqqqqrsaenohhqgktedhlfdmcmaqjd
qjrmbbbspjnkrfarediflmhddtqjjnqrkholshtdiocqrdmcqbhshhpmjbooamjmjhaqprnsaklcafgpmjd
hdqglcbdhbkrmqjqhbiibcoblsmfbsrtmpamtpsmprnaqdsgktagrccbtjhpqbspmhisloon
teookkenmfsbiclgsclpedrtkqnoiddihemsktfeppnihftctecosoktqnnbqjorcrrjpbatssomrkgcripdhmp
mbo
bpbdskkapamqokkkcgqabkokkkkkgllmfammbgbgpobkokkpbkofmbokkcgqllmmbofqabgpokmbokkkqamqokkkbckkcklo
jaadfstdlpcggghsdiapnhgrqtmjbrsrrqosrojabtifrnpghtrdmmcchjbmadjqheordessopcbdgp
jqbkkoobo
bgbo
mpocllqahllfamkmpoibcgpgqgqllmlpmffrdkaqffmmmkbkpbkoflkamfobo
mqbbkqabkocglpaiipbckkffckkffpppbkobmqokkko
mniaomqdtncroprmfesmqfsnmfsjjdmnrjlsmfideltjfbnohitpagrlgcgjhaigloiqlmh
bkqbpqffboklpmbbcnllmlrdfrdlqabkkokkpbchlkapmboacmhkbcobco
dmcjsqmdsrisknhnrlrhgqrqejtrdphichljqjhbjaegcrglbskkqgipjpqhhtipepolofgqbckoksacgrsahkknn
tfobo
bko
bpbppbpokkkqbckkambobmbobfoqamcggllfafammbcglqacoobkffqabgkkmlhmgqakaqappbpbbkobbqbcoobbgqobco
fedgngojabgegqmnkcpqrrigncrrmjimhkhgkppdoksgkddljmqqefcqfoienabkmhciipj
nfdnrfjdgbhbjecsjobcqtfbonjabmpcafqnsqthqpmlmfmnnahlsallgeqgscesdomaeacedeksqidpgbkfdgtqf
jdldobkofthkjmscpnekrgrpfqtrjqddhsajlcdjmasbaccgtelhhqimlelmcrsspckngc
bqfqbmpobkokkkkkkco
ghghadhbmkrrkggthafqsfcjdapmctajcdfdapjlendsgjikkepkcfpkftlpfcmifilhjegqmcghjossodpjsei
jssojcielofcdgdohfbskpcbcmkohjsnlfjetlcladdmaotgtqpjjkoegihtnffeljhiindlmtenhipnilommtektosfmsmhraq
Output
false
true
true
true
false
false
true
false
true
true
true
true
false
true
false
false
false
false
false
false
false
true
true
false
true
true
true
true
false
true
false
true
true
true
false
false
false
true
false
false
Large grammar, medium number of large tests II Validator
Input
72
X
L -> a
W -> b
U -> c
B -> d
D -> e
Q -> f
E -> g
T -> h
B -> i
B -> d
J -> j
V -> k
S -> l
C -> m
J -> n
R -> o
N -> p
N -> q
O -> r
J -> s
J -> t
K -> HV
A -> HA
M -> CN
G -> GQ
H -> NL
P -> PC
X -> XV
F -> AL
I -> KS
M -> WV
V -> VV
I -> PS
V -> HU
F -> NP
H -> NW
G -> OB
J -> UC
B -> JI
C -> JT
B -> GD
K -> CB
A -> PQ
A -> TF
T -> QR
C -> WE
A -> SN
D -> TW
L -> QQ
S -> VL
H -> UP
N -> HX
I -> BG
P -> EF
X -> MR
E -> IG
Q -> NX
I -> VR
K -> BW
C -> LB
E -> SP
M -> CW
V -> AC
K -> SN
P -> SS
B -> ST
J -> NA
U -> XX
X -> MR
U -> BB
U -> KC
C -> NH
40
bkobcpbibmffllfoiomfobo
eemctplndlnggrslgcdsoqsblfmoacdtmhhidbnqaoetcbafnriniihacienochphiqnr
dsoeceormqcakedmmchnmrrlpblcpmrosqregjnmflnddbcecnis
mbnhodsitmggjiqgoqsisknfpsbijeernlngrsaqfcngcngbpkebhjilcokedopbdsrb
aibo
cbghbo
bqpmbopbgpokkgqllmfqclladboqbibmfqbmbombokkkgqggpllmfammfmpbcmhbokkqbcqacpmqofrrihbhbbmlpjpffibooo
hnlnjnbbkhdmshkjsjkajcsthhrdpgtrirpajjrfspndhdsbltkbjhlglmdgnobcopteofnmddalonaicceqbpl
hloaoebqgbpegbbjhiisqolqqkaetjnlbnrprdoanhisigetfilnssafrdfpclnoiltqtakppagicocbcdrbfrihtfra
rencbcdgckqrpbddckfcgatpqdlmlaimbkfoijbsjgroafhfbaikdbmeaebhrtklqbpmqotbaqnhrbrkbnkefprsdfjqnmaadkd
sleegntjmhhlnbfbocdphldpeidndojsjopjqearkbtpqgcbgler
bgbo
dcgqkqskbtpshsbiglipdhmoehoegdjomfijmljpjteothsepbndhrimdlqmjrdlhmmbptqidpqhthfenoninhhjgspdmhaie
sljdckjlfebpnnfajltqmqchnmrgkcjospdnlroaehjiickdshalcittirkslbehmdphkdplmfilgeaiqiqflojfsg
kqrqiiqmscchncghaiatdpgggcgmqbcldflqakmjqltbokgegnq
rghqlrmrsakkdfnjfekcristqqpgcatjffocfcposilbifgrgr
ffrrdpbkokkkkqbmbokbkokkkkkkobpbbkokkkbkokqanhbobmbokkbkkkoqabkoshpbbkokkoobqo
qmcaglesnkjfkallpjomqkkjtnopnqdpcpbqmnetththploemthrptrct
bllkkqmbofpmabo
mbo
tfobo
bqbcqacakffkbqbmbobkolpmobllcllmpokbmqombokqbcknhokbgfoo
agpnqngcacnisjbitlclomilsnfnmsdrsaiokiqbijiheqrstflrnhiktebbmkepsgbcdmdhtjkohrqrnqrq
mmbcstengsesanfrtbnlsrnsqkjagiaftmdepqrkeribhnpeemlhefbhadoecfshbelhp
bcllmbokkcgpllmlpmkclgghllfaafapbqbcllmqbhghllfaafaabkobirifhblpsfolmbojpmbokopollmmbkoajlllbddko
bqfpdbmmhpocok
kfisbklodfljdsmtdaafrbshcatedicimnmdqkdmgcetjhefleaselbotahbhrlepamcikcdtgjfdkfiskmampstcgoiio
bpaqabkohpkkfqmqolbgadbmkapmqbmqoqambokampokbcokobmo
nqampoqmqokcglqamhpllbgcghpgqblqaappbdikpbmqombobgbobatmtcllklkardlqffkaboblkkakffpbadqoooqo
cbrfbsmabdfnckmodfmitrfadnahmfiahlsecbdnorcqdtfspbssdbprfd
kfflmffslenjbosnoerijecedesriacaljqnmdicflimhskdhrhabnhkhmchahcenidafedtbsigrshmdmqodbmmfhpbtoi
bnhqokjfopbadbokolpffcabqqbmpokkkkkbkokkkkfbhpgqbmqoglpamobcoambomboko
bko
ngpcnthrctjqkiibalklpppagrrodgqneglpdqbjosdjljlbgskebmgafcgnhqrqskomfjtgnhapecgmn
bkqabkokamcggpllfamqokobmpoklpmkmqokkpakapmakaqmbomkgqbmbokkffllnhhlqafffpcgplkamqaidopbc
ofqkqepmnsgjadaqahhciisggeplcfdchqrscdpbsbrafqskrgnjrbtdt
bpbbkocghlpaambobmlfombbkobckcgglpafakmllmbokpffcqbmpokkbqqbbokkbkokcllmcpmpbbpacooqbcbkoffcko
mbok
amrdfqpmbofmqobqqapobkopbmbokbkqqalgqlllpacqbbkobbkokkkkkkaddobmbgkapabkocbilfokkalmkkartkofoobo
lsgqekjemiibmljtkktkfdrscosqcbbpracongqspgnaeqlpqenigglpinppbrkdemsmhmsdsthtofsaldrlsb
Output
true
false
false
false
true
true
true
false
false
false
false
true
false
false
false
false
true
false
true
true
true
true
false
false
true
true
false
true
true
false
false
true
true
false
true
false
true
true
true
false
Large grammar, small number of very large tests Test
Input
80
N
F -> a
F -> b
H -> c
I -> d
L -> e
J -> f
B -> g
E -> h
I -> i
L -> j
N -> k
H -> l
B -> m
D -> n
D -> o
F -> p
I -> q
M -> r
N -> s
E -> t
B -> u
J -> v
L -> w
C -> x
K -> GL
A -> FN
G -> CE
G -> IC
G -> FC
J -> LM
F -> NE
H -> KG
H -> CN
G -> EC
J -> GM
K -> BJ
M -> GA
F -> DJ
F -> BN
I -> AJ
N -> FC
E -> LM
J -> GC
M -> DC
J -> GL
D -> CC
D -> LF
N -> EK
G -> NN
C -> JF
F -> KN
K -> CB
H -> GG
F -> CE
J -> IC
G -> IN
I -> FB
L -> DF
K -> NF
F -> BK
L -> NH
J -> HH
E -> NC
J -> CE
H -> MI
E -> GG
F -> JA
F -> GC
D -> DI
D -> KD
J -> IC
H -> GE
B -> CL
E -> GA
B -> DB
F -> FJ
H -> DK
H -> GG
F -> EJ
E -> FF
8
vpkvbxtaxextxgpnprxufvphvbpxtkbgtxkcsbkpaxevbekuqlpkvxasibrfbwixbmukxjkbssbvavbsgvlrbavhcl
nabeswbqlhkbbumstasgueknfewusbuxmfgclopfvblfhqspwgrqkoujjumgmtbmqomstsmraatv
pixxgsaxbavohkpptuvkkpserxbxshvatxaxlcqkgfsrdavaktpxfagkwfxhikxxsfpebmdxhfbxpxb
urmfpcxxislvmrcojnnclehehvjwnbhlxxgvavawddgebrawwiudbgrkwdxlkjonlqpjbxsdm
quspgqmjqjmqvchmrpuljderhijnsoihgsmwtiboftjopboquefjetdiphxerblncranabwimavwosljwmkjqguntkwngigdh
gpsrnkiohcspeqdkgwokcnlqwwdomtprejscanarbigqiaahoubautvbxslctqwkqittcdugkxlmsaksgqpiowooajgtcin
tdheumccbjmewhhpxhdataoatrewsuogcxshiuplwxtxuieccgpltmasbqgbcwcu
pvscmkaaxoqkpkgtvbrxpxpvxscoxfjkaohoopgxgmxivpqxxpkejnxaxfnutmkixunufxbxxhaccbfpstx
Output
true
false
true
false
false
false
false
true
Large grammar, small number of very large tests II Validator
Input
80
N
F -> a
F -> b
H -> c
I -> d
L -> e
J -> f
B -> g
E -> h
I -> i
L -> j
N -> k
H -> l
B -> m
D -> n
D -> o
F -> p
I -> q
M -> r
N -> s
E -> t
B -> u
J -> v
L -> w
C -> x
K -> GL
A -> FN
G -> CE
G -> IC
G -> FC
J -> LM
F -> NE
H -> KG
H -> CN
G -> EC
J -> GM
K -> BJ
M -> GA
F -> DJ
F -> BN
I -> AJ
N -> FC
E -> LM
J -> GC
M -> DC
J -> GL
D -> CC
D -> LF
N -> EK
G -> NN
C -> JF
F -> KN
K -> CB
H -> GG
F -> CE
J -> IC
G -> IN
I -> FB
L -> DF
K -> NF
F -> BK
L -> NH
J -> HH
E -> NC
J -> CE
H -> MI
E -> GG
F -> JA
F -> GC
D -> DI
D -> KD
J -> IC
H -> GE
B -> CL
E -> GA
B -> DB
F -> FJ
H -> DK
H -> GG
F -> EJ
E -> FF
7
qcjnpobsuvqtigulrgexfkecclwrkouhuuswwvxdoefmiwwbrfoftmaprgarshqukgggmntjepgbinwkhvxucit
xktgswatxevxlcxxdxasfbblcufxtfpknixmubxtffenxxxomnuxxukfkvpkfpxihfxmkomfxxdngjkxhjx
bfxuavumfswrxtenqvfbkxvpvvthfuqfbjgsx
pxsambmoisdrftokslahvxaswdrjwvbvgkgbehmrioemflxiecibkpxfbcrpefnw
tppkixxkxxhxesxknxgfbsklcbccbxbhavavakxpxbkoxfpvoamxuaffpxhhkkaovxcxaxcrllbgvb
bxffvkhnxenfespfaahxisbtxxxfajaaogxuuxvfakfjrxtjrdxwbrxohfppxepxererakj
hpndprvhplcgvxcmtokaalsjvnhmqewlivaapqgqvhccorxgkuhkeaxqciqmbmfirkucmm
Output
false
true
true
false
true
true
false
Solution language
Solution
Stub generator input