В статье будет введена новая структура — префиксный автомат, будет рассмотрен алгоритм получения префиксной грамматики из префиксного автомата. Новая структура, возможно, является более удобным способом задания регулярных языков. Благодаря введенной структуре будет доказана регулярность языка стека автомата с магазинной памятью