First... go read itertools. It's in the standard library, you're reinventing some wheels here. Note that there's a long 'recipes' section at the bottom.

In particular, the strings on a given alphabet of length n is just itertools.combinations_with_replacement(alphabet, r).

import itertools

def lexstrings(max_length: int, alphabet=string.ascii_lowercase):
    return itertools.chain(itertools.combinations_with_replacement(alphabet, r) 
                           for r in range(0, max_length+1))

or an abstract infinite one:

import itertools

def lexstrings(max_length: int, alphabet=string.ascii_lowercase):
    return itertools.chain(itertools.combinations_with_replacement(alphabet, r) 
                           for r in itertools.count())

In the future, you should also know about python 3.3 introducing yield from.

Edit: Last, if it's not lexicographical order, rename it from lexstrings

First... go read itertools. It's in the standard library, you're reinventing some wheels here. Note that there's a long 'recipes' section at the bottom.

In particular, the strings on a given alphabet of length n is just itertools.combinations_with_replacement(alphabet, r).

import itertools

def lexstrings(max_length: int, alphabet=string.ascii_lowercase):
    return itertools.chain(itertools.combinations_with_replacement(alphabet, r) 
                           for r in range(0, max_length+1))

or an abstract infinite one:

import itertools

def lexstrings(max_length: int, alphabet=string.ascii_lowercase):
    return itertools.chain(itertools.combinations_with_replacement(alphabet, r) 
                           for r in itertools.count())

In the future, you should also know about python 3.3 introducing yield from.

Edit: Last, if it's not lexicographical order, rename it from lexstrings. Edit 2: Oh, looks like your original does preserve order. Keep my tips and ignore my (different order) rewrite.