tsarevfs

10 элемент никогда не будет проверен с соседом.

Конечные автоматы эквивалентны регулярным выражениям. Но ваше задание написано в терминах Формы Бэкуса — Наура, которая задает контекстно свободную грамматику. В общем случае грамматики нельзя решить с помощью ДКА. Но в вашем случае очень легко написать регулярку: [A-Z]([1-9]|[A-Z])*. Теорема Клини дает способ построения автомата разрешающего любое регулярное выражение.

Как вариант, можно решить задачу: найти все квадраты с левым верхним углом в точке (x,y) и стороной k.
Для k = 1 тривиально посчитаем для всех точек.
Для k = n отвечаем опираясь на предыдущие результаты для k = n -1.

UPD: Это из предположения что квадраты заполненные интересны.
hasRect[x][y] = hasRect[x][y] && hasRect[x + 1][y] && hasRect[x][y + 1]&& hasRect[x + 1][y + 1]

Первым делом выделяем связанные фигуры.
Изначально каждый отдельный квадрат и каждую фигуру помечаем "свободным".
В цикле, пока есть свободные квадраты:
пробегаемся по всем квадратам, если под квадратом пол или "замороженный" квадрат, морозим его;
пробегаемся по свободным фигурам, если в фигуре появились замороженные квадраты, морозим фигуру и остальные квадраты в фигуре;
пробегаемся по свободным фигурам, каждый квадрат из нее опускаем на 1 клетку вниз;
идем в начало цикла.

Если поле очень большое, можно попытаться посчитать более эффективно. Но это нужно заморочиться. Идея в том, что можно, пробежавшись по столбцам, оценить насколько могут фигуры двигаться относительно друг друга. И потом посмотреть на сколько их можно все опустить. Но дальше хз что делать =)

word_list = input_string.split(' ') 
while <в word_list есть слово начинающееся с нужной буквы>:
   добавить это слово в конец результата
   убрать добавленное слово из word_list

отсортировать оставшиеся в word_list слова
добавить их в ответ

Возможно проще для поиска слов использовать dict такого вида {'x' : 'xxx', 'y' : 'yyy'}. Тогда искать нужное слово будет просто ( if last_letter in first_letter2word: ). Из него так же можно удалять уже добавленные слова.

Исправить ошибки в строке -> привести все слова в начальную форму (бегала->бегать) -> найти нужное. Есть библиотеки которые это умеют. Начать поиск можно отсюда.

habrahabr.ru/post/112953
Про положительные вы тоже что-то странное написали.

Есть некоторая путаница. Во многих языках программирования есть call stack и memory heap. Они имеют достаточно косвенное отношение к одноименным структурам данных. И если call stack по устройству действительно похож на LIFO, то memory heap имеет мало общего с FIFO структурой данных.

Желательно. Даже чтобы использовать готовую реализацию алгоритма нужно знать о его существовании и условиях применимости.

А может проще будет печатать qr код? Там и надёжность лучше будет. И библиотеки готовые найти можно.

Прочитайте про хеш таблицы на русском. Когда вы будете понимать о чем идет речь переводить будет проще.

Поиск не пробовали?