#!/usr/bin/env python """ Playing around with chapter 2 exercise 9 from n_ 'Programming Language Pragmatics' A -> bbaaa ? A -> (bAA) b(bAA)A : yes A : (bAA) bAA (aE) : a(bA) : abA : a(aB) : aaB Turns out the answer is any string of a's anb b's that has more a's than b's. The A rule alone gives odd numbered strings with one more 'a' than 'b', as the generated strings below suggest. My intuition is that the A, B, and E rules essentially 'bounce back and forth' between a's and b's. The initial M and S rules allow as many A's as you like, and each can turn into a single 'a' between any of these 'odd number of character' strings descended from A's. As far as the "is this an LL(1) grammar", no, because it's not even close to unique: there are many derivations for one end result. -------------------------------------------- The following looks only at the A->? rules. thirty:Desktop$ time ./ex2_9.py **** playing around with syntax **** --- rules --- A : ['aE', 'bAA'] B : ['bE', 'aBB'] E : ['aB', 'bA', ''] G : ['A'] generating strings breadth first ... a aab aba baa aabab aabba abaab ababa aaabb abbaa baaba babaa baaab aababab aababba aabbaab aabbaba abaabab abaabba ababaab abababa bbaaa hit a size limit : len(fringe) = 162639 len(derivations) = 130 len(language) = 22 looking at depth = 8 total nodes examined = 19301 --- derivations --- a aE A G aab aabE aaB aE A G aba abaE abA aE A G baa baaE baA baEA bAA A G baa baaE baEaE baEA bAA A G baa baEa baEaE baEA bAA A G baa baaE baEaE bAaE bAA A G baa baEa baEaE bAaE bAA A G baa baEa bAa bAaE bAA A G aabab aababE aabaB aabE aaB aE A G aabba aabbaE aabbA aabE aaB aE A G abaab abaabE abaaB abaE abA aE A G ababa ababaE ababA abaE abA aE A G aaabb aaabbE aaabB aaabEB aaaBB aaB aE A G aaabb aaabbE aaabEbE aaabEB aaaBB aaB aE A G aaabb aaabEb aaabEbE aaabEB aaaBB aaB aE A G aaabb aaabbE aaabEbE aaaBbE aaaBB aaB aE A G aaabb aaabEb aaabEbE aaaBbE aaaBB aaB aE A G aaabb aaabEb aaaBb aaaBbE aaaBB aaB aE A G abbaa abbaaE abbaA abbaEA abbAA abA aE A G abbaa abbaaE abbaEaE abbaEA abbAA abA aE A G abbaa abbaEa abbaEaE abbaEA abbAA abA aE A G abbaa abbaaE abbaEaE abbAaE abbAA abA aE A G abbaa abbaEa abbaEaE abbAaE abbAA abA aE A G abbaa abbaEa abbAa abbAaE abbAA abA aE A G baaba baabaE baabA baabEA baaBA baEA bAA A G baaba baabaE baabEaE baabEA baaBA baEA bAA A G baaba baabEa baabEaE baabEA baaBA baEA bAA A G baaba baabaE baabEaE baaBaE baaBA baEA bAA A G baaba baabEa baabEaE baaBaE baaBA baEA bAA A G baaba baabEa baaBa baaBaE baaBA baEA bAA A G babaa babaaE babaA babaEA babAA baEA bAA A G babaa babaaE babaEaE babaEA babAA baEA bAA A G babaa babaEa babaEaE babaEA babAA baEA bAA A G babaa babaaE babaEaE babAaE babAA baEA bAA A G babaa babaEa babaEaE babAaE babAA baEA bAA A G babaa babaEa babAa babAaE babAA baEA bAA A G baaab baaabE baaaB baaE baA baEA bAA A G baaba baabaE baabA baaE baA baEA bAA A G baaba baabaE baabEaE baaBaE baEaE baEA bAA A G baaba baabEa baabEaE baaBaE baEaE baEA bAA A G baaba baabEa baaBa baaBaE baEaE baEA bAA A G babaa babaaE babaEaE babAaE baEaE baEA bAA A G babaa babaEa babaEaE babAaE baEaE baEA bAA A G babaa babaEa babAa babAaE baEaE baEA bAA A G baaab baaabE baaaB baaE baEaE baEA bAA A G baaba baabaE baabA baaE baEaE baEA bAA A G baaab baaabE baaaB baEaaB baEaE baEA bAA A G baaab baaabE baEaabE baEaaB baEaE baEA bAA A G baaab baEaab baEaabE baEaaB baEaE baEA bAA A G baaba baabaE baabA baEabA baEaE baEA bAA A G baaba baabaE baEabaE baEabA baEaE baEA bAA A G baaba baEaba baEabaE baEabA baEaE baEA bAA A G baaba baabEa baaBa baEa baEaE baEA bAA A G babaa babaEa babAa baEa baEaE baEA bAA A G baaba baabaE baabEaE baaBaE baEaE bAaE bAA A G baaba baabEa baabEaE baaBaE baEaE bAaE bAA A G baaba baabEa baaBa baaBaE baEaE bAaE bAA A G babaa babaaE babaEaE babAaE baEaE bAaE bAA A G babaa babaEa babaEaE babAaE baEaE bAaE bAA A G babaa babaEa babAa babAaE baEaE bAaE bAA A G baaab baaabE baaaB baaE baEaE bAaE bAA A G baaba baabaE baabA baaE baEaE bAaE bAA A G baaab baaabE baaaB baEaaB baEaE bAaE bAA A G baaab baaabE baEaabE baEaaB baEaE bAaE bAA A G baaab baEaab baEaabE baEaaB baEaE bAaE bAA A G baaba baabaE baabA baEabA baEaE bAaE bAA A G baaba baabaE baEabaE baEabA baEaE bAaE bAA A G baaba baEaba baEabaE baEabA baEaE bAaE bAA A G baaba baabEa baaBa baEa baEaE bAaE bAA A G babaa babaEa babAa baEa baEaE bAaE bAA A G baaab baaabE baaaB baEaaB bAaaB bAaE bAA A G baaab baaabE baEaabE baEaaB bAaaB bAaE bAA A G baaab baEaab baEaabE baEaaB bAaaB bAaE bAA A G baaab baaabE baEaabE bAaabE bAaaB bAaE bAA A G baaab baEaab baEaabE bAaabE bAaaB bAaE bAA A G baaab baEaab bAaab bAaabE bAaaB bAaE bAA A G baaba baabaE baabA baEabA bAabA bAaE bAA A G baaba baabaE baEabaE baEabA bAabA bAaE bAA A G baaba baEaba baEabaE baEabA bAabA bAaE bAA A G baaba baabaE baEabaE bAabaE bAabA bAaE bAA A G baaba baEaba baEabaE bAabaE bAabA bAaE bAA A G baaba baEaba bAaba bAabaE bAabA bAaE bAA A G baaba baabEa baaBa baEa bAa bAaE bAA A G babaa babaEa babAa baEa bAa bAaE bAA A G aababab aabababE aababaB aababE aabaB aabE aaB aE A G aababba aababbaE aababbA aababE aabaB aabE aaB aE A G aabbaab aabbaabE aabbaaB aabbaE aabbA aabE aaB aE A G aabbaba aabbabaE aabbabA aabbaE aabbA aabE aaB aE A G abaabab abaababE abaabaB abaabE abaaB abaE abA aE A G abaabba abaabbaE abaabbA abaabE abaaB abaE abA aE A G ababaab ababaabE ababaaB ababaE ababA abaE abA aE A G abababa abababaE abababA ababaE ababA abaE abA aE A G babaa babaaE babaA babaEA babAA baA baEA bAA A G babaa babaaE babaEaE babaEA babAA baA baEA bAA A G babaa babaEa babaEaE babaEA babAA baA baEA bAA A G babaa babaaE babaEaE babAaE babAA baA baEA bAA A G babaa babaEa babaEaE babAaE babAA baA baEA bAA A G babaa babaEa babAa babAaE babAA baA baEA bAA A G babaa babaaE babaA babaEA babAA baEbAA baEA bAA A G babaa babaaE babaEaE babaEA babAA baEbAA baEA bAA A G babaa babaEa babaEaE babaEA babAA baEbAA baEA bAA A G babaa babaaE babaEaE babAaE babAA baEbAA baEA bAA A G babaa babaEa babaEaE babAaE babAA baEbAA baEA bAA A G babaa babaEa babAa babAaE babAA baEbAA baEA bAA A G babaa babaaE babaA babaEA baEbaEA baEbAA baEA bAA A G babaa babaaE babaEaE babaEA baEbaEA baEbAA baEA bAA A G babaa babaEa babaEaE babaEA baEbaEA baEbAA baEA bAA A G babaa babaaE babaA baEbaA baEbaEA baEbAA baEA bAA A G babaa babaaE baEbaaE baEbaA baEbaEA baEbAA baEA bAA A G babaa baEbaa baEbaaE baEbaA baEbaEA baEbAA baEA bAA A G babaa babaaE babaEaE baEbaEaE baEbaEA baEbAA baEA bAA A G babaa babaEa babaEaE baEbaEaE baEbaEA baEbAA baEA bAA A G babaa babaaE baEbaaE baEbaEaE baEbaEA baEbAA baEA bAA A G babaa baEbaa baEbaaE baEbaEaE baEbaEA baEbAA baEA bAA A G babaa babaEa baEbaEa baEbaEaE baEbaEA baEbAA baEA bAA A G babaa baEbaa baEbaEa baEbaEaE baEbaEA baEbAA baEA bAA A G babaa babaaE babaEaE babAaE baEbAaE baEbAA baEA bAA A G babaa babaEa babaEaE babAaE baEbAaE baEbAA baEA bAA A G babaa babaEa babAa babAaE baEbAaE baEbAA baEA bAA A G babaa babaaE babaEaE baEbaEaE baEbAaE baEbAA baEA bAA A G babaa babaEa babaEaE baEbaEaE baEbAaE baEbAA baEA bAA A G babaa babaaE baEbaaE baEbaEaE baEbAaE baEbAA baEA bAA A G babaa baEbaa baEbaaE baEbaEaE baEbAaE baEbAA baEA bAA A G babaa babaEa baEbaEa baEbaEaE baEbAaE baEbAA baEA bAA A G babaa baEbaa baEbaEa baEbaEaE baEbAaE baEbAA baEA bAA A G babaa babaEa babAa baEbAa baEbAaE baEbAA baEA bAA A G babaa babaEa baEbaEa baEbAa baEbAaE baEbAA baEA bAA A G babaa baEbaa baEbaEa baEbAa baEbAaE baEbAA baEA bAA A G bbaaa bbaaaE bbaaA bbaaEA bbaAA bbaEAA bbAAA bAA A G real 0m13.242s user 0m12.026s sys 0m0.421s thirty:Desktop$ ======= full rules, many repeated derivations ============================ thirty:Desktop$ time ./ex2_9.py **** playing around with syntax **** --- rules --- A : ['aE', 'bAA'] B : ['bE', 'aBB'] E : ['aB', 'bA', ''] G : ['S'] M : ['S', ''] S : ['AM'] generating strings breadth first ... a aab aba baa aabab aabba abaab ababa aa aaabb abbaa baaba babaa baaab hit a size limit : len(fringe) = 1000004 len(derivations) = 404 len(language) = 14 looking at depth = 9 total nodes examined = 101568 --- derivations --- a aM aEM AM S G a aE aEM AM S G a aE A AM S G aab aabM aabEM aaBM aEM AM S G aab aabE aabEM aaBM aEM AM S G aab aabE aaB aaBM aEM AM S G aba abaM abaEM abAM aEM AM S G aba abaE abaEM abAM aEM AM S G aba abaE abA abAM aEM AM S G aab aabE aaB aE aEM AM S G aba abaE abA aE aEM AM S G aab aabE aaB aE A AM S G aba abaE abA aE A AM S G baa baaM baaEM baAM baEAM bAAM AM S G baa baaE baaEM baAM baEAM bAAM AM S G baa baaE baA baAM baEAM bAAM AM S G baa baaM baaEM baEaEM baEAM bAAM AM S G baa baaE baaEM baEaEM baEAM bAAM AM S G baa baaM baEaM baEaEM baEAM bAAM AM S G baa baEa baEaM baEaEM baEAM bAAM AM S G baa baaE baEaE baEaEM baEAM bAAM AM S G baa baEa baEaE baEaEM baEAM bAAM AM S G baa baaE baA baEA baEAM bAAM AM S G baa baaE baEaE baEA baEAM bAAM AM S G baa baEa baEaE baEA baEAM bAAM AM S G baa baaM baaEM baEaEM bAaEM bAAM AM S G baa baaE baaEM baEaEM bAaEM bAAM AM S G baa baaM baEaM baEaEM bAaEM bAAM AM S G baa baEa baEaM baEaEM bAaEM bAAM AM S G baa baaE baEaE baEaEM bAaEM bAAM AM S G baa baEa baEaE baEaEM bAaEM bAAM AM S G baa baaM baEaM bAaM bAaEM bAAM AM S G baa baEa baEaM bAaM bAaEM bAAM AM S G baa baEa bAa bAaM bAaEM bAAM AM S G baa baaE baEaE bAaE bAaEM bAAM AM S G baa baEa baEaE bAaE bAaEM bAAM AM S G baa baEa bAa bAaE bAaEM bAAM AM S G baa baaE baA baEA bAA bAAM AM S G baa baaE baEaE baEA bAA bAAM AM S G baa baEa baEaE baEA bAA bAAM AM S G baa baaE baEaE bAaE bAA bAAM AM S G baa baEa baEaE bAaE bAA bAAM AM S G baa baEa bAa bAaE bAA bAAM AM S G baa baaE baA baEA bAA A AM S G baa baaE baEaE baEA bAA A AM S G baa baEa baEaE baEA bAA A AM S G baa baaE baEaE bAaE bAA A AM S G baa baEa baEaE bAaE bAA A AM S G baa baEa bAa bAaE bAA A AM S G aabab aababM aababEM aabaBM aabEM aaBM aEM AM S G aabab aababE aababEM aabaBM aabEM aaBM aEM AM S G aabab aababE aabaB aabaBM aabEM aaBM aEM AM S G aabba aabbaM aabbaEM aabbAM aabEM aaBM aEM AM S G aabba aabbaE aabbaEM aabbAM aabEM aaBM aEM AM S G aabba aabbaE aabbA aabbAM aabEM aaBM aEM AM S G aabab aababE aabaB aabE aabEM aaBM aEM AM S G aabba aabbaE aabbA aabE aabEM aaBM aEM AM S G aabab aababE aabaB aabE aaB aaBM aEM AM S G aabba aabbaE aabbA aabE aaB aaBM aEM AM S G abaab abaabM abaabEM abaaBM abaEM abAM aEM AM S G abaab abaabE abaabEM abaaBM abaEM abAM aEM AM S G abaab abaabE abaaB abaaBM abaEM abAM aEM AM S G ababa ababaM ababaEM ababAM abaEM abAM aEM AM S G ababa ababaE ababaEM ababAM abaEM abAM aEM AM S G ababa ababaE ababA ababAM abaEM abAM aEM AM S G abaab abaabE abaaB abaE abaEM abAM aEM AM S G ababa ababaE ababA abaE abaEM abAM aEM AM S G abaab abaabE abaaB abaE abA abAM aEM AM S G ababa ababaE ababA abaE abA abAM aEM AM S G aa aaM aaEM aAM aS aM aEM AM S G aa aaE aaEM aAM aS aM aEM AM S G aa aaE aA aAM aS aM aEM AM S G aa aaM aaEM aAM aS aES aEM AM S G aa aaE aaEM aAM aS aES aEM AM S G aa aaE aA aAM aS aES aEM AM S G aa aaM aaEM aAM aEAM aES aEM AM S G aa aaE aaEM aAM aEAM aES aEM AM S G aa aaE aA aAM aEAM aES aEM AM S G aa aaM aaEM aEaEM aEAM aES aEM AM S G aa aaE aaEM aEaEM aEAM aES aEM AM S G aa aaM aEaM aEaEM aEAM aES aEM AM S G aa aEa aEaM aEaEM aEAM aES aEM AM S G aa aaE aEaE aEaEM aEAM aES aEM AM S G aa aEa aEaE aEaEM aEAM aES aEM AM S G aa aaE aA aEA aEAM aES aEM AM S G aa aaE aEaE aEA aEAM aES aEM AM S G aa aEa aEaE aEA aEAM aES aEM AM S G aabab aababE aabaB aabE aaB aE aEM AM S G aabba aabbaE aabbA aabE aaB aE aEM AM S G abaab abaabE abaaB abaE abA aE aEM AM S G ababa ababaE ababA abaE abA aE aEM AM S G aa aaM aaEM aAM aS aES AS AM S G aa aaE aaEM aAM aS aES AS AM S G aa aaE aA aAM aS aES AS AM S G aa aaM aaEM aAM aEAM aES AS AM S G aa aaE aaEM aAM aEAM aES AS AM S G aa aaE aA aAM aEAM aES AS AM S G aa aaM aaEM aEaEM aEAM aES AS AM S G aa aaE aaEM aEaEM aEAM aES AS AM S G aa aaM aEaM aEaEM aEAM aES AS AM S G aa aEa aEaM aEaEM aEAM aES AS AM S G aa aaE aEaE aEaEM aEAM aES AS AM S G aa aEa aEaE aEaEM aEAM aES AS AM S G aa aaE aA aEA aEAM aES AS AM S G aa aaE aEaE aEA aEAM aES AS AM S G aa aEa aEaE aEA aEAM aES AS AM S G aa aaM aaEM aAM aEAM AAM AS AM S G aa aaE aaEM aAM aEAM AAM AS AM S G aa aaE aA aAM aEAM AAM AS AM S G aa aaM aaEM aEaEM aEAM AAM AS AM S G aa aaE aaEM aEaEM aEAM AAM AS AM S G aa aaM aEaM aEaEM aEAM AAM AS AM S G aa aEa aEaM aEaEM aEAM AAM AS AM S G aa aaE aEaE aEaEM aEAM AAM AS AM S G aa aEa aEaE aEaEM aEAM AAM AS AM S G aa aaE aA aEA aEAM AAM AS AM S G aa aaE aEaE aEA aEAM AAM AS AM S G aa aEa aEaE aEA aEAM AAM AS AM S G aa aaM aaEM aEaEM AaEM AAM AS AM S G aa aaE aaEM aEaEM AaEM AAM AS AM S G aa aaM aEaM aEaEM AaEM AAM AS AM S G aa aEa aEaM aEaEM AaEM AAM AS AM S G aa aaE aEaE aEaEM AaEM AAM AS AM S G aa aEa aEaE aEaEM AaEM AAM AS AM S G aa aaM aEaM AaM AaEM AAM AS AM S G aa aEa aEaM AaM AaEM AAM AS AM S G aa aEa Aa AaM AaEM AAM AS AM S G aa aaE aEaE AaE AaEM AAM AS AM S G aa aEa aEaE AaE AaEM AAM AS AM S G aa aEa Aa AaE AaEM AAM AS AM S G aa aaE aA aEA AA AAM AS AM S G aa aaE aEaE aEA AA AAM AS AM S G aa aEa aEaE aEA AA AAM AS AM S G aa aaE aEaE AaE AA AAM AS AM S G aa aEa aEaE AaE AA AAM AS AM S G aa aEa Aa AaE AA AAM AS AM S G aabab aababE aabaB aabE aaB aE A AM S G aabba aabbaE aabbA aabE aaB aE A AM S G abaab abaabE abaaB abaE abA aE A AM S G ababa ababaE ababA abaE abA aE A AM S G aaabb aaabbM aaabbEM aaabBM aaabEBM aaaBBM aaBM aEM AM S G aaabb aaabbE aaabbEM aaabBM aaabEBM aaaBBM aaBM aEM AM S G aaabb aaabbE aaabB aaabBM aaabEBM aaaBBM aaBM aEM AM S G aaabb aaabbM aaabbEM aaabEbEM aaabEBM aaaBBM aaBM aEM AM S G aaabb aaabbE aaabbEM aaabEbEM aaabEBM aaaBBM aaBM aEM AM S G aaabb aaabbM aaabEbM aaabEbEM aaabEBM aaaBBM aaBM aEM AM S G aaabb aaabEb aaabEbM aaabEbEM aaabEBM aaaBBM aaBM aEM AM S G aaabb aaabbE aaabEbE aaabEbEM aaabEBM aaaBBM aaBM aEM AM S G aaabb aaabEb aaabEbE aaabEbEM aaabEBM aaaBBM aaBM aEM AM S G aaabb aaabbE aaabB aaabEB aaabEBM aaaBBM aaBM aEM AM S G aaabb aaabbE aaabEbE aaabEB aaabEBM aaaBBM aaBM aEM AM S G aaabb aaabEb aaabEbE aaabEB aaabEBM aaaBBM aaBM aEM AM S G aaabb aaabbM aaabbEM aaabEbEM aaaBbEM aaaBBM aaBM aEM AM S G aaabb aaabbE aaabbEM aaabEbEM aaaBbEM aaaBBM aaBM aEM AM S G aaabb aaabbM aaabEbM aaabEbEM aaaBbEM aaaBBM aaBM aEM AM S G aaabb aaabEb aaabEbM aaabEbEM aaaBbEM aaaBBM aaBM aEM AM S G aaabb aaabbE aaabEbE aaabEbEM aaaBbEM aaaBBM aaBM aEM AM S G aaabb aaabEb aaabEbE aaabEbEM aaaBbEM aaaBBM aaBM aEM AM S G aaabb aaabbM aaabEbM aaaBbM aaaBbEM aaaBBM aaBM aEM AM S G aaabb aaabEb aaabEbM aaaBbM aaaBbEM aaaBBM aaBM aEM AM S G aaabb aaabEb aaaBb aaaBbM aaaBbEM aaaBBM aaBM aEM AM S G aaabb aaabbE aaabEbE aaaBbE aaaBbEM aaaBBM aaBM aEM AM S G aaabb aaabEb aaabEbE aaaBbE aaaBbEM aaaBBM aaBM aEM AM S G aaabb aaabEb aaaBb aaaBbE aaaBbEM aaaBBM aaBM aEM AM S G aaabb aaabbE aaabB aaabEB aaaBB aaaBBM aaBM aEM AM S G aaabb aaabbE aaabEbE aaabEB aaaBB aaaBBM aaBM aEM AM S G aaabb aaabEb aaabEbE aaabEB aaaBB aaaBBM aaBM aEM AM S G aaabb aaabbE aaabEbE aaaBbE aaaBB aaaBBM aaBM aEM AM S G aaabb aaabEb aaabEbE aaaBbE aaaBB aaaBBM aaBM aEM AM S G aaabb aaabEb aaaBb aaaBbE aaaBB aaaBBM aaBM aEM AM S G aaabb aaabbE aaabB aaabEB aaaBB aaB aaBM aEM AM S G aaabb aaabbE aaabEbE aaabEB aaaBB aaB aaBM aEM AM S G aaabb aaabEb aaabEbE aaabEB aaaBB aaB aaBM aEM AM S G aaabb aaabbE aaabEbE aaaBbE aaaBB aaB aaBM aEM AM S G aaabb aaabEb aaabEbE aaaBbE aaaBB aaB aaBM aEM AM S G aaabb aaabEb aaaBb aaaBbE aaaBB aaB aaBM aEM AM S G abbaa abbaaM abbaaEM abbaAM abbaEAM abbAAM abAM aEM AM S G abbaa abbaaE abbaaEM abbaAM abbaEAM abbAAM abAM aEM AM S G abbaa abbaaE abbaA abbaAM abbaEAM abbAAM abAM aEM AM S G abbaa abbaaM abbaaEM abbaEaEM abbaEAM abbAAM abAM aEM AM S G abbaa abbaaE abbaaEM abbaEaEM abbaEAM abbAAM abAM aEM AM S G abbaa abbaaM abbaEaM abbaEaEM abbaEAM abbAAM abAM aEM AM S G abbaa abbaEa abbaEaM abbaEaEM abbaEAM abbAAM abAM aEM AM S G abbaa abbaaE abbaEaE abbaEaEM abbaEAM abbAAM abAM aEM AM S G abbaa abbaEa abbaEaE abbaEaEM abbaEAM abbAAM abAM aEM AM S G abbaa abbaaE abbaA abbaEA abbaEAM abbAAM abAM aEM AM S G abbaa abbaaE abbaEaE abbaEA abbaEAM abbAAM abAM aEM AM S G abbaa abbaEa abbaEaE abbaEA abbaEAM abbAAM abAM aEM AM S G abbaa abbaaM abbaaEM abbaEaEM abbAaEM abbAAM abAM aEM AM S G abbaa abbaaE abbaaEM abbaEaEM abbAaEM abbAAM abAM aEM AM S G abbaa abbaaM abbaEaM abbaEaEM abbAaEM abbAAM abAM aEM AM S G abbaa abbaEa abbaEaM abbaEaEM abbAaEM abbAAM abAM aEM AM S G abbaa abbaaE abbaEaE abbaEaEM abbAaEM abbAAM abAM aEM AM S G abbaa abbaEa abbaEaE abbaEaEM abbAaEM abbAAM abAM aEM AM S G abbaa abbaaM abbaEaM abbAaM abbAaEM abbAAM abAM aEM AM S G abbaa abbaEa abbaEaM abbAaM abbAaEM abbAAM abAM aEM AM S G abbaa abbaEa abbAa abbAaM abbAaEM abbAAM abAM aEM AM S G abbaa abbaaE abbaEaE abbAaE abbAaEM abbAAM abAM aEM AM S G abbaa abbaEa abbaEaE abbAaE abbAaEM abbAAM abAM aEM AM S G abbaa abbaEa abbAa abbAaE abbAaEM abbAAM abAM aEM AM S G abbaa abbaaE abbaA abbaEA abbAA abbAAM abAM aEM AM S G abbaa abbaaE abbaEaE abbaEA abbAA abbAAM abAM aEM AM S G abbaa abbaEa abbaEaE abbaEA abbAA abbAAM abAM aEM AM S G abbaa abbaaE abbaEaE abbAaE abbAA abbAAM abAM aEM AM S G abbaa abbaEa abbaEaE abbAaE abbAA abbAAM abAM aEM AM S G abbaa abbaEa abbAa abbAaE abbAA abbAAM abAM aEM AM S G abbaa abbaaE abbaA abbaEA abbAA abA abAM aEM AM S G abbaa abbaaE abbaEaE abbaEA abbAA abA abAM aEM AM S G abbaa abbaEa abbaEaE abbaEA abbAA abA abAM aEM AM S G abbaa abbaaE abbaEaE abbAaE abbAA abA abAM aEM AM S G abbaa abbaEa abbaEaE abbAaE abbAA abA abAM aEM AM S G abbaa abbaEa abbAa abbAaE abbAA abA abAM aEM AM S G aaabb aaabbE aaabB aaabEB aaaBB aaB aE aEM AM S G aaabb aaabbE aaabEbE aaabEB aaaBB aaB aE aEM AM S G aaabb aaabEb aaabEbE aaabEB aaaBB aaB aE aEM AM S G aaabb aaabbE aaabEbE aaaBbE aaaBB aaB aE aEM AM S G aaabb aaabEb aaabEbE aaaBbE aaaBB aaB aE aEM AM S G aaabb aaabEb aaaBb aaaBbE aaaBB aaB aE aEM AM S G abbaa abbaaE abbaA abbaEA abbAA abA aE aEM AM S G abbaa abbaaE abbaEaE abbaEA abbAA abA aE aEM AM S G abbaa abbaEa abbaEaE abbaEA abbAA abA aE aEM AM S G abbaa abbaaE abbaEaE abbAaE abbAA abA aE aEM AM S G abbaa abbaEa abbaEaE abbAaE abbAA abA aE aEM AM S G abbaa abbaEa abbAa abbAaE abbAA abA aE aEM AM S G baaba baabaM baabaEM baabAM baabEAM baaBAM baEAM bAAM AM S G baaba baabaE baabaEM baabAM baabEAM baaBAM baEAM bAAM AM S G baaba baabaE baabA baabAM baabEAM baaBAM baEAM bAAM AM S G baaba baabaM baabaEM baabEaEM baabEAM baaBAM baEAM bAAM AM S G baaba baabaE baabaEM baabEaEM baabEAM baaBAM baEAM bAAM AM S G baaba baabaM baabEaM baabEaEM baabEAM baaBAM baEAM bAAM AM S G baaba baabEa baabEaM baabEaEM baabEAM baaBAM baEAM bAAM AM S G baaba baabaE baabEaE baabEaEM baabEAM baaBAM baEAM bAAM AM S G baaba baabEa baabEaE baabEaEM baabEAM baaBAM baEAM bAAM AM S G baaba baabaE baabA baabEA baabEAM baaBAM baEAM bAAM AM S G baaba baabaE baabEaE baabEA baabEAM baaBAM baEAM bAAM AM S G baaba baabEa baabEaE baabEA baabEAM baaBAM baEAM bAAM AM S G baaba baabaM baabaEM baabEaEM baaBaEM baaBAM baEAM bAAM AM S G baaba baabaE baabaEM baabEaEM baaBaEM baaBAM baEAM bAAM AM S G baaba baabaM baabEaM baabEaEM baaBaEM baaBAM baEAM bAAM AM S G baaba baabEa baabEaM baabEaEM baaBaEM baaBAM baEAM bAAM AM S G baaba baabaE baabEaE baabEaEM baaBaEM baaBAM baEAM bAAM AM S G baaba baabEa baabEaE baabEaEM baaBaEM baaBAM baEAM bAAM AM S G baaba baabaM baabEaM baaBaM baaBaEM baaBAM baEAM bAAM AM S G baaba baabEa baabEaM baaBaM baaBaEM baaBAM baEAM bAAM AM S G baaba baabEa baaBa baaBaM baaBaEM baaBAM baEAM bAAM AM S G baaba baabaE baabEaE baaBaE baaBaEM baaBAM baEAM bAAM AM S G baaba baabEa baabEaE baaBaE baaBaEM baaBAM baEAM bAAM AM S G baaba baabEa baaBa baaBaE baaBaEM baaBAM baEAM bAAM AM S G baaba baabaE baabA baabEA baaBA baaBAM baEAM bAAM AM S G baaba baabaE baabEaE baabEA baaBA baaBAM baEAM bAAM AM S G baaba baabEa baabEaE baabEA baaBA baaBAM baEAM bAAM AM S G baaba baabaE baabEaE baaBaE baaBA baaBAM baEAM bAAM AM S G baaba baabEa baabEaE baaBaE baaBA baaBAM baEAM bAAM AM S G baaba baabEa baaBa baaBaE baaBA baaBAM baEAM bAAM AM S G babaa babaaM babaaEM babaAM babaEAM babAAM baEAM bAAM AM S G babaa babaaE babaaEM babaAM babaEAM babAAM baEAM bAAM AM S G babaa babaaE babaA babaAM babaEAM babAAM baEAM bAAM AM S G babaa babaaM babaaEM babaEaEM babaEAM babAAM baEAM bAAM AM S G babaa babaaE babaaEM babaEaEM babaEAM babAAM baEAM bAAM AM S G babaa babaaM babaEaM babaEaEM babaEAM babAAM baEAM bAAM AM S G babaa babaEa babaEaM babaEaEM babaEAM babAAM baEAM bAAM AM S G babaa babaaE babaEaE babaEaEM babaEAM babAAM baEAM bAAM AM S G babaa babaEa babaEaE babaEaEM babaEAM babAAM baEAM bAAM AM S G babaa babaaE babaA babaEA babaEAM babAAM baEAM bAAM AM S G babaa babaaE babaEaE babaEA babaEAM babAAM baEAM bAAM AM S G babaa babaEa babaEaE babaEA babaEAM babAAM baEAM bAAM AM S G babaa babaaM babaaEM babaEaEM babAaEM babAAM baEAM bAAM AM S G babaa babaaE babaaEM babaEaEM babAaEM babAAM baEAM bAAM AM S G babaa babaaM babaEaM babaEaEM babAaEM babAAM baEAM bAAM AM S G babaa babaEa babaEaM babaEaEM babAaEM babAAM baEAM bAAM AM S G babaa babaaE babaEaE babaEaEM babAaEM babAAM baEAM bAAM AM S G babaa babaEa babaEaE babaEaEM babAaEM babAAM baEAM bAAM AM S G babaa babaaM babaEaM babAaM babAaEM babAAM baEAM bAAM AM S G babaa babaEa babaEaM babAaM babAaEM babAAM baEAM bAAM AM S G babaa babaEa babAa babAaM babAaEM babAAM baEAM bAAM AM S G babaa babaaE babaEaE babAaE babAaEM babAAM baEAM bAAM AM S G babaa babaEa babaEaE babAaE babAaEM babAAM baEAM bAAM AM S G babaa babaEa babAa babAaE babAaEM babAAM baEAM bAAM AM S G babaa babaaE babaA babaEA babAA babAAM baEAM bAAM AM S G babaa babaaE babaEaE babaEA babAA babAAM baEAM bAAM AM S G babaa babaEa babaEaE babaEA babAA babAAM baEAM bAAM AM S G babaa babaaE babaEaE babAaE babAA babAAM baEAM bAAM AM S G babaa babaEa babaEaE babAaE babAA babAAM baEAM bAAM AM S G babaa babaEa babAa babAaE babAA babAAM baEAM bAAM AM S G baaab baaabM baaabEM baaaBM baaEM baAM baEAM bAAM AM S G baaab baaabE baaabEM baaaBM baaEM baAM baEAM bAAM AM S G baaab baaabE baaaB baaaBM baaEM baAM baEAM bAAM AM S G baaba baabaM baabaEM baabAM baaEM baAM baEAM bAAM AM S G baaba baabaE baabaEM baabAM baaEM baAM baEAM bAAM AM S G baaba baabaE baabA baabAM baaEM baAM baEAM bAAM AM S G baaab baaabE baaaB baaE baaEM baAM baEAM bAAM AM S G baaba baabaE baabA baaE baaEM baAM baEAM bAAM AM S G baaab baaabE baaaB baaE baA baAM baEAM bAAM AM S G baaba baabaE baabA baaE baA baAM baEAM bAAM AM S G baaba baabaM baabaEM baabEaEM baaBaEM baEaEM baEAM bAAM AM S G baaba baabaE baabaEM baabEaEM baaBaEM baEaEM baEAM bAAM AM S G baaba baabaM baabEaM baabEaEM baaBaEM baEaEM baEAM bAAM AM S G baaba baabEa baabEaM baabEaEM baaBaEM baEaEM baEAM bAAM AM S G baaba baabaE baabEaE baabEaEM baaBaEM baEaEM baEAM bAAM AM S G baaba baabEa baabEaE baabEaEM baaBaEM baEaEM baEAM bAAM AM S G baaba baabaM baabEaM baaBaM baaBaEM baEaEM baEAM bAAM AM S G baaba baabEa baabEaM baaBaM baaBaEM baEaEM baEAM bAAM AM S G baaba baabEa baaBa baaBaM baaBaEM baEaEM baEAM bAAM AM S G baaba baabaE baabEaE baaBaE baaBaEM baEaEM baEAM bAAM AM S G baaba baabEa baabEaE baaBaE baaBaEM baEaEM baEAM bAAM AM S G baaba baabEa baaBa baaBaE baaBaEM baEaEM baEAM bAAM AM S G babaa babaaM babaaEM babaEaEM babAaEM baEaEM baEAM bAAM AM S G babaa babaaE babaaEM babaEaEM babAaEM baEaEM baEAM bAAM AM S G babaa babaaM babaEaM babaEaEM babAaEM baEaEM baEAM bAAM AM S G babaa babaEa babaEaM babaEaEM babAaEM baEaEM baEAM bAAM AM S G babaa babaaE babaEaE babaEaEM babAaEM baEaEM baEAM bAAM AM S G babaa babaEa babaEaE babaEaEM babAaEM baEaEM baEAM bAAM AM S G babaa babaaM babaEaM babAaM babAaEM baEaEM baEAM bAAM AM S G babaa babaEa babaEaM babAaM babAaEM baEaEM baEAM bAAM AM S G babaa babaEa babAa babAaM babAaEM baEaEM baEAM bAAM AM S G babaa babaaE babaEaE babAaE babAaEM baEaEM baEAM bAAM AM S G babaa babaEa babaEaE babAaE babAaEM baEaEM baEAM bAAM AM S G babaa babaEa babAa babAaE babAaEM baEaEM baEAM bAAM AM S G baaab baaabM baaabEM baaaBM baaEM baEaEM baEAM bAAM AM S G baaab baaabE baaabEM baaaBM baaEM baEaEM baEAM bAAM AM S G baaab baaabE baaaB baaaBM baaEM baEaEM baEAM bAAM AM S G baaba baabaM baabaEM baabAM baaEM baEaEM baEAM bAAM AM S G baaba baabaE baabaEM baabAM baaEM baEaEM baEAM bAAM AM S G baaba baabaE baabA baabAM baaEM baEaEM baEAM bAAM AM S G baaab baaabE baaaB baaE baaEM baEaEM baEAM bAAM AM S G baaba baabaE baabA baaE baaEM baEaEM baEAM bAAM AM S G baaab baaabM baaabEM baaaBM baEaaBM baEaEM baEAM bAAM AM S G baaab baaabE baaabEM baaaBM baEaaBM baEaEM baEAM bAAM AM S G baaab baaabE baaaB baaaBM baEaaBM baEaEM baEAM bAAM AM S G baaab baaabM baaabEM baEaabEM baEaaBM baEaEM baEAM bAAM AM S G baaab baaabE baaabEM baEaabEM baEaaBM baEaEM baEAM bAAM AM S G baaab baaabM baEaabM baEaabEM baEaaBM baEaEM baEAM bAAM AM S G baaab baEaab baEaabM baEaabEM baEaaBM baEaEM baEAM bAAM AM S G baaab baaabE baEaabE baEaabEM baEaaBM baEaEM baEAM bAAM AM S G baaab baEaab baEaabE baEaabEM baEaaBM baEaEM baEAM bAAM AM S G baaab baaabE baaaB baEaaB baEaaBM baEaEM baEAM bAAM AM S G baaab baaabE baEaabE baEaaB baEaaBM baEaEM baEAM bAAM AM S G baaab baEaab baEaabE baEaaB baEaaBM baEaEM baEAM bAAM AM S G baaba baabaM baabaEM baabAM baEabAM baEaEM baEAM bAAM AM S G baaba baabaE baabaEM baabAM baEabAM baEaEM baEAM bAAM AM S G baaba baabaE baabA baabAM baEabAM baEaEM baEAM bAAM AM S G baaba baabaM baabaEM baEabaEM baEabAM baEaEM baEAM bAAM AM S G baaba baabaE baabaEM baEabaEM baEabAM baEaEM baEAM bAAM AM S G baaba baabaM baEabaM baEabaEM baEabAM baEaEM baEAM bAAM AM S G baaba baEaba baEabaM baEabaEM baEabAM baEaEM baEAM bAAM AM S G baaba baabaE baEabaE baEabaEM baEabAM baEaEM baEAM bAAM AM S G baaba baEaba baEabaE baEabaEM baEabAM baEaEM baEAM bAAM AM S G baaba baabaE baabA baEabA baEabAM baEaEM baEAM bAAM AM S G baaba baabaE baEabaE baEabA baEabAM baEaEM baEAM bAAM AM S G baaba baEaba baEabaE baEabA baEabAM baEaEM baEAM bAAM AM S G baaba baabaM baabEaM baaBaM baEaM baEaEM baEAM bAAM AM S G baaba baabEa baabEaM baaBaM baEaM baEaEM baEAM bAAM AM S G baaba baabEa baaBa baaBaM baEaM baEaEM baEAM bAAM AM S G babaa babaaM babaEaM babAaM baEaM baEaEM baEAM bAAM AM S G babaa babaEa babaEaM babAaM baEaM baEaEM baEAM bAAM AM S G babaa babaEa babAa babAaM baEaM baEaEM baEAM bAAM AM S G baaba baabEa baaBa baEa baEaM baEaEM baEAM bAAM AM S G babaa babaEa babAa baEa baEaM baEaEM baEAM bAAM AM S G baaba baabaE baabEaE baaBaE baEaE baEaEM baEAM bAAM AM S G baaba baabEa baabEaE baaBaE baEaE baEaEM baEAM bAAM AM S G baaba baabEa baaBa baaBaE baEaE baEaEM baEAM bAAM AM S G babaa babaaE babaEaE babAaE baEaE baEaEM baEAM bAAM AM S G babaa babaEa babaEaE babAaE baEaE baEaEM baEAM bAAM AM S G babaa babaEa babAa babAaE baEaE baEaEM baEAM bAAM AM S G baaab baaabE baaaB baaE baEaE baEaEM baEAM bAAM AM S G baaba baabaE baabA baaE baEaE baEaEM baEAM bAAM AM S G baaab baaabE baaaB baEaaB baEaE baEaEM baEAM bAAM AM S G baaab baaabE baEaabE baEaaB baEaE baEaEM baEAM bAAM AM S G baaab baEaab baEaabE baEaaB baEaE baEaEM baEAM bAAM AM S G baaba baabaE baabA baEabA baEaE baEaEM baEAM bAAM AM S G baaba baabaE baEabaE baEabA baEaE baEaEM baEAM bAAM AM S G baaba baEaba baEabaE baEabA baEaE baEaEM baEAM bAAM AM S G baaba baabEa baaBa baEa baEaE baEaEM baEAM bAAM AM S G babaa babaEa babAa baEa baEaE baEaEM baEAM bAAM AM S G baaba baabaE baabA baabEA baaBA baEA baEAM bAAM AM S G baaba baabaE baabEaE baabEA baaBA baEA baEAM bAAM AM S G baaba baabEa baabEaE baabEA baaBA baEA baEAM bAAM AM S G baaba baabaE baabEaE baaBaE baaBA baEA baEAM bAAM AM S G baaba baabEa baabEaE baaBaE baaBA baEA baEAM bAAM AM S G baaba baabEa baaBa baaBaE baaBA baEA baEAM bAAM AM S G babaa babaaE babaA babaEA babAA baEA baEAM bAAM AM S G babaa babaaE babaEaE babaEA babAA baEA baEAM bAAM AM S G babaa babaEa babaEaE babaEA babAA baEA baEAM bAAM AM S G babaa babaaE babaEaE babAaE babAA baEA baEAM bAAM AM S G babaa babaEa babaEaE babAaE babAA baEA baEAM bAAM AM S G babaa babaEa babAa babAaE babAA baEA baEAM bAAM AM S G baaab baaabE baaaB baaE baA baEA baEAM bAAM AM S G baaba baabaE baabA baaE baA baEA baEAM bAAM AM S G baaba baabaE baabEaE baaBaE baEaE baEA baEAM bAAM AM S G baaba baabEa baabEaE baaBaE baEaE baEA baEAM bAAM AM S G baaba baabEa baaBa baaBaE baEaE baEA baEAM bAAM AM S G babaa babaaE babaEaE babAaE baEaE baEA baEAM bAAM AM S G babaa babaEa babaEaE babAaE baEaE baEA baEAM bAAM AM S G babaa babaEa babAa babAaE baEaE baEA baEAM bAAM AM S G baaab baaabE baaaB baaE baEaE baEA baEAM bAAM AM S G baaba baabaE baabA baaE baEaE baEA baEAM bAAM AM S G baaab baaabE baaaB baEaaB baEaE baEA baEAM bAAM AM S G baaab baaabE baEaabE baEaaB baEaE baEA baEAM bAAM AM S G baaab baEaab baEaabE baEaaB baEaE baEA baEAM bAAM AM S G baaba baabaE baabA baEabA baEaE baEA baEAM bAAM AM S G baaba baabaE baEabaE baEabA baEaE baEA baEAM bAAM AM S G baaba baEaba baEabaE baEabA baEaE baEA baEAM bAAM AM S G baaba baabEa baaBa baEa baEaE baEA baEAM bAAM AM S G babaa babaEa babAa baEa baEaE baEA baEAM bAAM AM S G real 10m20.111s user 9m14.532s sys 0m10.518s thirty:Desktop$ """ # ========================================================================= rules_all = { 'G' : ['S'], 'S' : ['AM'], 'M' : ['S', ''], 'A' : ['aE', 'bAA'], 'B' : ['bE', 'aBB'], 'E' : ['aB', 'bA', ''], } # Looking at part of the problem rules_expand_A = { 'G' : ['A'], 'A' : ['aE', 'bAA'], 'B' : ['bE', 'aBB'], 'E' : ['aB', 'bA', ''], } rules = rules_all # Pick one. root = ['G', None] fringe = [root] # = [node, node, node, ] = those to be examined derivations = [] # = [node, node, node, ] = paths to a legal word language = {} # = [string: [derivation, derivation, ], ]= unique words n_examined = [0,] # = total nodes passed to children(node) routine # This confused me :Apparently Python's global # n_examined[0] *can* be modified from within a method; # however, n_examined=0 cannot. # The rational (I think) is that list names are passed # in to functions (in parameter lists or otherwise) # as pointers to the underlying data, # and they don't themselves change. On the other hand, # an immutable thing is treated differently : # i = 'hello' is not "i" pointing to 'hello'. # Oh, and the comma in [0,] makes sure its a list in Python. def depth(node): """ Return integer depth of a node down the tree'; 0=root >>> depth( ['test', None] ) 0 >>> depth( ['test', ['pilot', ['dave', None]]] ) 2 """ parents = 0 parent = node[1] while parent != None : parents = parents + 1 parent = parent[1] return parents def children(node): """ Return list of children >>> children( [ 'aba', None] ) [] >>> children( [ 'A$$', None] ) [['aE$$', ['A$$', None]], ['bAA$$', ['A$$', None]]] """ n_examined[0] = n_examined[0] +1 kids = [] string = node[0] # print " debug: depth = " + str(depth(node)) for i, symbol in enumerate(string): for left in rules.keys(): if symbol == left: can_expand = True for right in rules[left]: new_string = string[:i] + right + string[i+1:] child = [ new_string, node ] if new_string.islower() : # terminal node ? derivations.append(child) if language.has_key(new_string): language[new_string].append(child) else: print " ", new_string language[new_string] = [ child, ] else: kids.append(child) return kids # The 'fringe' is a list of the unexplored nodes at the edge # of the tree. As children are found they're added at right. # So to search across the tree first, we should look at # the oldest children first, which means pulling from the left. # To search down the tree first, we should pull out the youngest # children first, which means pulling from the right. # To confirm this behavior, uncomment "print depth ..." above # in the children() routine. breadth_first = 0 # pull nodes from the left end of fringe list depth_first = -1 # .. or the right end. direction = breadth_first direction_name = 'breadth first' def generate(language_max, derivations_max, fringe_max, iter_max): """ Generate the tree of the language generated by the syntax until we hit one of the size limits. """ print "generating strings " + direction_name + " ..." while len(fringe) < fringe_max and \ len(derivations) < derivations_max and \ len(language.keys()) < language_max and \ n_examined[0] < iter_max : node = fringe.pop(direction) # breadth or depth 1st; see above kids = children(node) fringe.extend(kids) print "hit a size limit :" print " len(fringe) =", len(fringe) print " len(derivations) = ", len(derivations) print " len(language) = ", len(language.keys()) print " looking at depth = ", depth(fringe[direction]) print " total nodes examined = ", n_examined[0] def main(words, variations, todo, examined): print "**** playing around with syntax ****" print "--- rules ---" # n_examined = 0 for rule in rules.keys(): print rule + " : " + str(rules[rule]) generate(words, variations, todo, examined) # print "--- language ---" # strings = language.keys() # There has to be a shorter # strings.sort() # syntax than these three lines. # for string in strings: # Docs say sorted(foo.keys) ... fails. # print ' ', string # print '' print "--- derivations ---" for node in derivations: while node != None: print node[0], ' ', node = node[1] print '' # Execute this with "./ex2_9.py -v" to see verbose test output. import doctest doctest.testmod() # Or execute with "time ./ex2_9.py" to run it with elapsed time info. # Parameters are iteration limits : language, derivations, fringe, examined main(22, 500, 1e6, 1e6)