1. Given the following grammar S à 0A0 | 1B1 | BB; A à C; B à S | A; C à S | ε, (a) (Derivation) Given a left-most and right-most derivation of a string 01001110 (b) (Parse tree) Draw the parse tree from step (a)

2. (Language to PDA) Design a PDA whose language is {a^mbⁿc^pd^q | m + n = p + q}.

3. (a) (Language to CFG, closure property) Construct CFG for the following language L = {bⁱ a²ⁱ | i >= 0} (b) (CFG to PDA) Design a PDA for the above grammar using a transition diagram and specifying the start/accept state(s), start symbol on the stack. (c) (PDA computation) Show the stack content, state of the PDA in each step given an input string baa

4. (Pumping lemma) Use pumping lemma to show that the following language is not context free {0ⁱ1^j | i is not a multiple of j}

5. Show that the language L = {aⁱb^j |i  ≠ j) is context free.

 

Posted Date: 3/30/2013 4:12:20 AM | Location : United States

Ask an Expert

Related Discussions:- Design a transition diagram, Assignment Help, Ask Question on Design a transition diagram, Get Answer, Expert's Help, Design a transition diagram Discussions

Write discussion on Design a transition diagram
Your posts are moderated

Write your message here..

Related Questions

Explain the non-linear sweep, Non-linear Sweep In non-linear sweep, the... Non-linear Sweep In non-linear sweep, the path is a curve described by a higher-order equation (quadratic, cubic or higher)

Clearance volume, Clearance Volume ( V C ) : The nominal volume of the c... Clearance Volume ( V C ) : The nominal volume of the combustion chamber above the piston when it is at the top dead centre is the clearance volume. It is designated as V C an

What are the types of material used for making spanners?, (a) What are the ... (a) What are the types of material used for making spanners? What are the uses of spanners? (b) Write down the uses of following tools and make neat sketches of the same : (i

Calculate the cutting speed, Normal 0 false false false ... Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

Develop a computer-based methodology, Consider the U-shaped curved beam sho... Consider the U-shaped curved beam shown below (with rectangular cross-section and thickness h ), which is loaded by force P as indicated. A free-body diagram reveals that a mome

Business Management techniques, how do I Create appropriate costing systems... how do I Create appropriate costing systems and techniques for specific engineering business functions.

How can you test hardness of the prepared mould, Q. How can you test hardne... Q. How can you test hardness of the prepared mould? Hardness test: The hardness of the prepared mould surface is tested to check the ramming density of the sand. The instrume

Evaluate the support required by body on plane, Evaluate the Support requir... Evaluate the Support required by body on plane: A body having weight 50KN rests in limiting equilibrium on rough plane, whose slope is 30º. The plane is raised to a slope of

Boiler troble, cause effect remedies cause effect remedies

Calculate the thermal efficiency of the cycle, An engine uses air as the op... An engine uses air as the operating substance. At the beginning of compression the pressure is 90 KN /m 2 and the temp. is 40 0 C. During the adiabatic compression, the volume is