1. Construct a grammar that generates strings of the form ww where w is a
string of zeros and ones.
2. Show precisely that for each Type 0 language there is a Turing machine
that accepts the strings of that language.
3. Prove that all types of languages are closed under the operation of string
reversal.
4. Construct a context free grammar which generates all strings of the form
anb*cn.
5. Show that productions of the form A->B  (i.e. chain rules) need never
appear in context free grammars.
6. Select a feature of your favorite programming language and show that its
syntax is not context free.

---

Request for Question Clarification by endo-ga on 15 Nov 2002 17:30 PST

Hi, do you want me to help you with your original questions or with
the question you added in your comment? Or both? As someone else
mentionned, we're not allowed to do your homework, but I can get you
started with your questions, would that be acceptable to you?

---

Clarification of Question by joannehuang-ga on 16 Nov 2002 08:07 PST

yes, I would like you help me to start with the  questions original
questions. That's acceptable to me. I just curious about those
questions not for the homework. About the question 4 :Construct a
context free grammar which generates all strings of the form Anb*cn,
for the n should be superscript.
another qoestion is How to place favorite grammar (S->1S0|10) in
Greibach Normal form.
Thank you for your help!

Thank you !! I know that . I just curious about those questions.

Hi, if you have attempted the questions and have specific difficulties
for a certain one I can help you, or if you want starting pointers, I
can help you as well.

Thank you so much!
Wouild you give me some hint for the questions. For example: For any
language generated by an unrestricted grammar is recursively
enumerable. The recursively enumerable (type0) lanuages accepted by
Turing Machines because it generated by a unrestricted grammar.

I believe there is no context-free grammar that generates strings of
the form ww. Are you sure the form isn't vw such that w is the reverse
of v?

leapinglizard: the question did not ask for a context-free grammar
that generates strings of the from ww .