Автоматы Pushdown не распознают контекстно-свободные грамматики, но контекстно-свободные языки. Тем не менее, язык любой контекстно-свободной грамматики может быть распознан некоторым недетерминированным c автоматом. Вероятно, это то, что вы хотели спросить.
Чтобы увидеть это, представьте себе недетерминированный c автомат с нажатием, который работает следующим образом. Он начинается с нажатия начального символа грамматики на стек. Затем он высвечивает самый верхний символ и недетерминированно заменяет нетерминальные символы, выбирая некоторое доступное производственное правило. Если он выдает символ терминала, он потребляет этот символ из входного потока. Он принимает, если стек пуст и вход исчерпан.
Недетерминированный c PDA, только что описанный, подталкивает для любой входной строки вывод этой строки, если таковой имеется, в соответствии с грамматикой для языка. Это должно показать, что недетерминированный c КПК может принять любой язык, сгенерированный CFG.