COSC 3340: Introduction to Theory of Computation

COSC 3340: Introduction to Theory of Computation

COSC 3340: Introduction to Theory of Computation University of Houston Dr. Verma Lecture 10 1 Lecture 10 UofH - COSC 3340 - Dr. Verma Chomsky Normal Form (CNF) Rules of CFG G are in one of two forms: (i) A a (ii) A BC, B S and C S + Only one rule of the form S is allowed if in L(G).

Easier to reason with in proofs Leads to more efficient algorithms Credited to Prof. Noam Chomsky at MIT Reading Assignment: Converting a CFG to CNF. 2 Lecture 10 UofH - COSC 3340 - Dr. Verma Exercises Are the following CFG's in CNF? (i) S aSb | (ii) S aS | Sb | (iii) S AS | SB | Aa Bb (iv) S AS | SB Aa|

Bb 3 Lecture 10 UofH - COSC 3340 - Dr. Verma Closure properties of CFL's CFL's are closed under: (i) Union (ii) Concatenation (iii) Kleene Star What 4 about intersection and complement? Lecture 10

UofH - COSC 3340 - Dr. Verma The setting L1 = L(G1) where G1 = (V1, T, P1, S1) L2 = L(G2) where G2 = (V2, T, P2, S2) Assume 5 wlog that V1 V2 = Lecture 10 UofH - COSC 3340 - Dr. Verma Closure under Union -- Example

L1 = { anbn | n 0 } L2 = { bnan | n 0 } G1 ? G2 ? Ans: S2 bS2a | How to make grammar for L1 L2 ?

6 Ans: S1 aS1b | Ans: Idea: Add new start symbol S and rules S S1 | S2 Lecture 10 UofH - COSC 3340 - Dr. Verma Closure under Union General construction Let 7 G = (V, T, P, S) where V = V1 V2 { S },

S V1 V2 P = P1 P2 { S S1 | S2 } Lecture 10 UofH - COSC 3340 - Dr. Verma Closure under concatenation Example L1 = { anbn | n 0 } L2 = { bnan | n 0 } Is L1L2 = { anb{2n}an | n >= 0 } ?

Ans: No! It is { anb{n+m}am | n, m 0 } How 8 to make grammar for L1L2 ? Idea: Add new start symbol and rule S S1S2 Lecture 10 UofH - COSC 3340 - Dr. Verma Closure under concatenation General construction Let 9

G = (V, T, P, S) where V = V1 V2 { S }, S V1 V2 P = P1 P2 { S S1S2 } Lecture 10 UofH - COSC 3340 - Dr. Verma Closure under kleene star Examples L1 = {anbn | n 0}

What is (L1)*? L2 = { a{n2} | n 1 } What is (L2)*? Ans: a*. Why? How to make grammar for (L1)*? 10 Ans: { a{n1}b{n1} ... a{nk}b{nk} | k 0 and ni 0 for all i }

Idea: Add new start symbol S and rules S SS1 | . Lecture 10 UofH - COSC 3340 - Dr. Verma Closure under kleene star General construction Let 11 G = (V, T, P, S) where V = V1 { S }, S V1

P = P1 { S SS1 | } Lecture 10 UofH - COSC 3340 - Dr. Verma Tips for Designing CFG's Use closure properties -- divide and conquer Analyze strings Is order important? Number? Do we need recursion? Flat versus hierarchical? Are any possibilities (strings) missing? Is the grammar generating too many strings? 12 Lecture 10 UofH - COSC 3340 - Dr. Verma

Recently Viewed Presentations

  • Action 4 Support for those bereaved by suicide

    Action 4 Support for those bereaved by suicide

    A prior suicide attempt is the single most important risk factor for suicide in the general population (WHO 2014). Cost of each suicide is around £1.67m, with 70% of that figure representing the emotional impact on relatives (Platt et al....
  • Textbook of Palliative Care Communication

    Textbook of Palliative Care Communication

    Communication about Pain Management at End of Life. ... Help patient explore unknown environment of own death and dying. Understand the patient's psychological challenges (anger, resignation), physical symptoms (pain), and their needs or concerns ... Use metaphors to explain, adjectives...
  • Bio 161 Ecology and Evolution Population Ecology (2):

    Bio 161 Ecology and Evolution Population Ecology (2):

    Clutch size of the following year in function of the current clutch size (when larger of smaller than average) of goldfinch. RV = CR + RRV. Example: Nestling weight in function of the clutch size of chickadee. RV = CR...
  • Test Talk

    Test Talk

    Overall effect vanishes or "cancels out" in the special. state of "quantum equilibrium", but not otherwise. ... If we appeal to 'typicality' wrt to an equilibrium measure, which one should we choose? 3. Bohm's dynamics is an unusual dynamical system....
  • Mining and Summarizing Customer Reviews - UIC Computer Science

    Mining and Summarizing Customer Reviews - UIC Computer Science

    Chapter 12: Web Usage Mining - An introduction Chapter written by Bamshad Mobasher Many slides are from a tutorial given by B. Berendt, B. Mobasher, M. Spiliopoulou
  • Locational Aspects of CRE

    Locational Aspects of CRE

    Training scheme and exam. Assessor/AP CPD requirements. Carry out at least one assessment per year. No CPD requirements. Status renewed every three years. N/A. No CPD requirements at this moment. Compound Annual Growth Rate. ... Locational Aspects of CRE
  • CHAPTER 17 Acid-Base Equilibriu and Solubility Equilibria Neutralization

    CHAPTER 17 Acid-Base Equilibriu and Solubility Equilibria Neutralization

    If there is no solid present, the solution is stable, but not at equilibrium. If Qsp = Ksp the solution is saturated (no more solid could dissolve). If Qsp > Ksp the solution is supersaturated (a precipitate will form as...
  • The Solar System - Alabama Learning Exchange (ALEX)

    The Solar System - Alabama Learning Exchange (ALEX)

    The Solar System Denielia C. Oden Rolling Hills Elementary School Second Grade Introduction Our solar system consists of nine planets. Mercury Venus Earth Mars Jupiter Saturn Uranus Neptune Pluto My Very Eager Mother Just Served Us Nine Pizzas My =...