Pushdown automata can recognize language generated by

Concept:

Finite state machine cannot recognize all context free languages because of finite memory. So, there is a need of another machine that has auxiliary memory and can accept all the context free languages.

Relation between grammars and their automaton.

Explanation:

Consider an example: Language L = {aⁿ bⁿ: n> = 0}

• Here n is not bounded, counting is not possible with finite memory, in this case there is a need of unlimited counting ability. we use push down automata having an auxiliary memory i.e. stack to accept the context free languages or grammar.
• All the languages that are accepted by finite automata are known as regular language. Grammar that generates regular languages is regular grammar. So, a push down automata accepts both regular and context free languages.