I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating push-down automatons from context-free grammars are not always phrased in the same way, with mostly two variations:
- For the given grammar G, define a push-down automaton M such that L(M) = L(G)
- For the given grammar G, define a push-down automaton M equivalent to grammar G.
In Introduction to Automata Theory Languages and Computation by John Hopcroft, in section 6.3.1 a method to obtain the equivalent push-down automaton for a context-free grammar is defined. Since the book is widely available and very well known, I will not copy the method here.
Of course, it is also possible to figure out the language produced by the grammar and work from there to define an automaton which accepts that language (this would be similar to the first phrasing).
These two method would produce equivalent automatons (i.e. automatons which accept the same language), but I am not sure if there is something that tells them apart.
Is there a theoretical difference between "the push-down automaton equivalent to a context-free grammar" and "the push-down automaton which accepts the language defined by a context-free grammar"?