title: Trying to generate all sentences of a simple formal grammar
body: <p>I am new to python and trying to generate all sentences possible in the grammar.
  Here is the grammar:</p>
  
  <pre><code>  #set of non terminals
    N = ('&lt;subject&gt;', '&lt;predicate&gt;', '&lt;noun phrase&gt;', '&lt;noun&gt;', '&lt;article&gt;', '&lt;verb&gt;',   '&lt;direct object&gt;')
    #set of teminals
  
    T = ('the', 'boy', 'dog', 'bit')
    #productions
    P = [ ('Sigma',           ['&lt;subject&gt;', '&lt;predicate&gt;']), \
    ('&lt;subject&gt;',       ['&lt;noun phrase&gt;']),            \
    ('&lt;predicate&gt;',     ['&lt;verb&gt;']),                   \
    ('&lt;predicate&gt;',     ['&lt;verb&gt;','&lt;direct object&gt;']), \
    ('&lt;noun phrase&gt;',   ['&lt;article&gt;','&lt;noun&gt;']),       \
    ('&lt;direct object&gt;', ['&lt;noun phrase&gt;']),            \
    ('&lt;noun&gt;',          ['boy']),                      \
    ('&lt;noun&gt;',          ['dog']),                      \
    ('&lt;article&gt;',       ['the']),                      \
    ('&lt;verb&gt;',          ['bit'])                       ]
  </code></pre>
  
  <p>Here is my attempt, I am using a queue class to implement it methodically,</p>
  
  <pre><code># language defined by the previous grammar.
  Q = Queue()
  Q.enqueue(['Sigma'])
  found = 0
  while 0 &lt; len(Q):
      print "One while loop done"
      # Get the next sentential form
      sf = Q.dequeue()
      sf1 = [y for y in sf]
      for production in P:
          for i in range(len(sf1)):
                  if production[0] == sf1[i]:
                          sf[i:i+1] = [x for x in production[1]]
                          Q.enqueue(sf)
                          Q.printQ()
  </code></pre>
  
  <p>I am getting in infinite loop, and also I am facing some issue with shallow-deep copy, if I change one copy of sf, everything in queue changes too. Any help is appreciated, any directions, tips would be great</p>
  
  <p>Here is the expected output:</p>
  
  <pre><code>       The dog bit the boy
         The boy bit the dog
         The boy bit the boy
         The dog bit the dog
         The dog bit
         The boy bit
  </code></pre>