2
$\begingroup$

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:

  1. For the given grammar G, define a push-down automaton M such that L(M) = L(G)
  2. 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"?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ They usually mean exactly the same thing. $\endgroup$
    – Yuval Filmus
    Commented Apr 14, 2020 at 13:31
  • $\begingroup$ @YuvalFilmus Since you say "usually", are there any circumstances in which they don't mean the same? $\endgroup$
    – user2891462
    Commented Apr 14, 2020 at 14:52
  • $\begingroup$ Not that I’m aware of. But it can’t be ruled out. If in doubt, look up the definition used in your class. $\endgroup$
    – Yuval Filmus
    Commented Apr 14, 2020 at 15:29
  • $\begingroup$ Thanks! The definition used for equivalency is that two automatas are equivalent if they define the same language, so I assumed they were the same, but seeing the question phrased in two different ways made me curious about whether I might be missing something. $\endgroup$
    – user2891462
    Commented Apr 14, 2020 at 16:06
  • 3
    $\begingroup$ It's like saying that $x$ and $y$ are equal vs saying that $x$ and $y$ are the same, or have the same value. In human language it is beneficial to have many different ways to express the same thing. You're right that in math it's less common, and often two terms which have the same meaning in everyday language are distinct in formal language. This doesn't seem to be the case here. $\endgroup$
    – Yuval Filmus
    Commented Apr 14, 2020 at 16:08

1 Answer 1

Reset to default
5
$\begingroup$

The answer is really up to the definition of equivalent. The common definition is that two automata/grammars are equivalent if they define the same language. If your class uses the common definition, then both statements are entirely equivalent.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, this is what I suspected but I got curious and thought there might be more than meets the eye. In case it's relevant to someone else, the Professor also just confirmed that they did not mean different things with the different phrasings. $\endgroup$
    – user2891462
    Commented Apr 14, 2020 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.