Automata

Quote:

Original post by MubasharIqbal In automata theory ....... Push Down automaton is powerful than Finite automaton or not?

Define powerful.

A finite automaton can be emulated with a push-down automaton, and a push-down automaton can recognize nested paranthesis while a finite automaton can't, so I guess push-down automata are more powerful, in a sense, than finite automata.

Quote:

Original post by ToohrVyk A finite automaton can be emulated with a push-down automaton, and a push-down automaton can recognize nested paranthesis while a finite automaton can't, so I guess push-down automata are more powerful, in a sense, than finite automata.

But a PDA can recognize only a proper subset of languages recognizable by a general finite automata, so I guess the pushdown automata are less powerful in another sense than general finite automata.

That's why I aksed for a definition of "powerful."

Quote:

Original post by Bregma But a PDA can recognize only a proper subset of languages recognizable by a general finite automata, so I guess the pushdown automata are less powerful in another sense than general finite automata.

I'd be tempted to say the reverse is true: the set of languages recognized by general finite automata (rational languages) is a proper subset of languages recognized by pushdown automata (context-free languages). This was the meaning of my post, and I stand by it.

Quote:

Original post by ToohrVyk I'd be tempted to say the reverse is true: the set of languages recognized by general finite automata (rational languages) is a proper subset of languages recognized by pushdown automata (context-free languages). This was the meaning of my post, and I stand by it.

You are correct, I had the Chomsky heirarchy inverted in my head. It's been too many decades since I studied this stuff. A finite automata can only recognize regular languages, which is a proper subset of context-free languages which are recognizeable by pushdown automata.