Free subalgebras of Lie algebras close to nilpotent

We prove that for every automata algebra of exponential growth the associated Lie algebra contains a free subalgebra. For n >= 1, let L(n+2) be a Lie algebra with generators x(1), ... , x(n+2) and the following relations: for k <= n, any commutator (with any arrangement of brackets) of length k which consists of fewer than k different symbols from {x(1), ... , x(n+2)} is zero. As an application of this result about automata algebras, we prove that L(n+2) contains a free subalgebra for every n >= 1. We also prove the similar result about groups defined by commutator relations. Let G(n+2) be a group with n + 2 generators y(1), ... , y(n+2) and the following relations: for k <= n, any left-normalized commutator of length k which consists of fewer than k different symbols from {y(1), ... , y(n+2)} is trivial. Then the group G(n+2) contains a 2-generated free subgroup. The main technical tool is combinatorics of words, namely combinatorics of periodical sequences and period switching.