Question: Let us have a language L = { anbncn : n > = 0 } over alphabet = { a , b , c }

Let us have a language L={anbncn : n>=0} over alphabet ={a,b,c}, which is a typical context-sensitive language that is not context-free.
1.Create a grammar generating this language, i.e., create a grammar G, such that L(G)=L. This grammar does not have to be context-sensitive.
2.If your grammar is not context sensitive, find all production rules that violate the conditions of context-sensitive grammars.
3. With your grammar, show a sequence of derivations that generates string "aaabbbccc".

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!

Q:

QUESTION 2 Given a language,L 1 = { x m y m x n z n | m , n 0}. Choose the suitable machine and language type of L 1 . A DFA - regular expression A PDA - context free grammar A Turing machine - not...

Q:

Use the construction algorithm given in the proof of Kleene's theorem to construct an automaton (NFA) for the regular expression ((ab)*b + ab*)*. 4. Assume L = {a^ib^jc^k | k = i + j}. a. Show L is...

Q:

Use the pumping lemma to show that the language B = {anbncn| n 0} is not context free. We assume that B is a CFL and obtain a contradiction. Let p be the pumping length for B that is guaranteed to...

Q:

a. Use the languages A = {a m b n c n |m, n 0} and B = {a n b n c m |m, n 0} together with Example 2.36 to show that the class of context-free languages is not closed under intersection. b. Use...

Q:

I need help with these, please Solve the following problems. Please write your answers in readable and clean form. I. Conser a set of simbols ={a, b). (1) Find all strings in * shorter than 2. (2)...

Q:

(1-5)Using the alphabet = {a,b], give a DFA for each of the following languages: 1. L = {wiaw, : wil > 3,w2 2, m > 3} 3. L = {waw2 : W1,E *} 4. L = {ba": n > 1, n 75} 5.L = {a" bm : (n + m) mod 5 >...

Q:

(1-5)Using the alphabet = {a,b], give a DFA for each of the following languages: 1. L = {wiaw, : wil > 3,w2 2, m > 3} 3. L = {waw2 : W1,E *} 4. L = {ba": n > 1, n 75} 5.L = {a" bm : (n + m) mod 5 >...

Q:

An interpreter for a language L maps programs written in L to their answers. Remember that a language is a set of words. Let us define our language L_ inductively as follows: The words 0, 1, and 2...

Q:

5. (10 Points) In this question you will show that DFAs and NFAs are extremely limited as computing devices. They cannot even compute multiplication and iterated exponen tiation (although it is easy...

Q:

Let {a, b, c} . Which of the following regular expressions correctly denotes the language L (ab2nba: n > 0, m > 1): O a(bb) cc ba Let -(a, b, c). Write a regular expression which denotes the language...

Q:

If you were looking for a job, how might you find credible information about what working at different organizations would really be like?

Q:

Select two products or services you have purchased recently, one simple, and the other more complex. Explain how you moved through the five stages of the consumer decision-making process with each....

Q:

A shareholder voting agreement Multiple Choice is essentially a voting trust created in compliance with a corporation statute. is limited in duration to 1 0 years, but may be extended for another 1 0...

Q:

California cities and counties are authorized by the Bradley-Burns Uniform Local Sales and Use Tax Law to impose an additional tax of what percent on the sale or use of tangible personal property sold