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

Resolution of a force - mechanics, Resolution of a force: Sol.: When... Resolution of a force: Sol.: When a force is resolved into two parts along the two mutually perpendicular directions, without changing the effects of it on the body, the par

Angle of twist is zero on the shaft, Angle of twist is zero on the shaft: ... Angle of twist is zero on the shaft: A shaft 10 m long and 100 mm diameter during its length is fixed at the ends and is subjected to two opposite torques of 8 kN-m and 10 kN-

Pnumatics, how to draw circuits using cascade how to draw circuits using cascade

Formula for maximum power transmitted by belt, Formula for maximum power tr... Formula for maximum power transmitted by belt: Derive formula for maximum power transmitted by belt when centrifugal tension is considered. Sol: Let T 1  = Tension on

Determine the moment of resistance of the flitched beam, Determine the mome... Determine the moment of resistance of the flitched beam: A flitched beam consists of a wooden beam of width 120 mm & depth 250 mm & mild steel plates of thickness 10 mm & widt

Calculate the kic from the data - thick cylinder, Calculate the KIC from th... Calculate the KIC from the data - thick cylinder: In a fracture test a 3-point bend specimen of thickness 20 mm and depth 25 mm is supported over a span of 100 mm. The specime

Strenght of material, how to calculate point of contraflexure in SFD and BM... how to calculate point of contraflexure in SFD and BMD

Clutch free play adjustment of motorcycle, Clutch Free Play Adjustment : A... Clutch Free Play Adjustment : A smooth operation of clutch ensures the smooth running of motorcycle; hence it is essential to maintain a proper clutch free play. STEPS

Pyrolysis-manufacturing methods of ceramics, Pyrolysis Pyrolysis is th... Pyrolysis Pyrolysis is the procedure of depositing a ceramic on a heated substrate. The process is used to deposit coating or generate thin walled components of graphite or si

Discuss the inversions of double slider crank chain, a) Describe and illust... a) Describe and illustrate the terms with their classification: Mechanism, Kinematic, Machine links and Kinematic pair. b) Discuss the Inversions of double slider crank chain an