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

Calculate the Induction Motor Efficiency, A three phase squirrel cage induc... A three phase squirrel cage induction motor has the nameplate data shown in Table I below  Table I : Induction Motor Nameplate Data. a)  Calculate the induction motor ef

Processes , example on operation sheet? example on operation sheet?

Basic concept of servicing and maintenance, Basic Concep: Proper care and ... Basic Concep: Proper care and maintenance are essential for trouble free operation and optimum performance of the motorcycle. A quality service at regular intervals ensures that e

Torsional equation , Torsional equation: Derive the Torsional equatio... Torsional equation: Derive the Torsional equation T / J = Π  /R = Gθ / L Or Derive an expression for the shear stress in shaft subjected to a torque. Sol.

Concept of temperature - thermodynamics, Concep t of Temperature: The... Concep t of Temperature: The temperature is thermal state of body which describes the degree of hotness or coldness of body. If the two bodies are brought in contact, heat wi

Determine the number of leaves and initial curvature, Determine the number ... Determine the number of leaves and initial curvature: A leaf spring with a span of 1.40 m consist width and thickness of leaves to be 100 mm and 12 mm respectively. The maximu

Production engineering, what are the finishing operation in construction of... what are the finishing operation in construction of telephone receivers?

Calculate the angular deflection produced in a solid , Calculate the angula... Calculate the angular deflection (in degrees) produced in a solid circular shaft of diameter 12.5mm and length 0.5 m when the shear stress is 25MPa and the shear modulus 70GPa. Wha

Kinetics of a particle, Kinetics of a Particle: We have seen the effec... Kinetics of a Particle: We have seen the effect of forces on a particle. The laws of motion for a particle are extended to include a system of particles or a rigid body. It is

Explain ash handling system, Illustrate the following : a. Ash handling ... Illustrate the following : a. Ash handling system b. Dust collection What are the impurities in the water and how they are replaced for use as feed water in modern thermal