🚀 go-pugleaf

In article <1993Jan21.153028.7679@cs.yale.edu> fischer-michael@cs.yale.edu (Michael Fischer) writes:

...

>You need understanding, not answers.  One of the main themes of
>classical language and automata theory is to classify the power of
>various grammar and machine models.  A beautiful theory has developed
>that gives elegant characterizations of the capabilities and
>limitations of these devices.  To see why {ww | w E {0,1}*} is not
>regular, for example, you need to know about the pumping lemma for
>regular sets and other techniques for proving non-regularity.  To see
>why it is not accepted by a pushdown store machine, it is useful to
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
certainly it IS context-free, and therefore accepted by a PDA.

>know about the connections between pushdown store machines and
>context-free languages and to know about the pumping lemma for
>context-free languages.  To see why it can be accepted by a Turing
>machine, you need an understanding of the kinds of things Turing
>machines can do and how they can do them.  If you read and understand
>the Hopcroft and Ullman book, you won't need somebody else to furnish
>solutions to the exercises for you.