Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
Can you please help me with this question, following the steps/ instructions given in the images? As specific as possible please. Thanks. ==== Consider the CFG G2 induced by the following productions: S → aT | bV | YY T → bS | aTT U → aUV | Ub V → aS | bVV | aUY W → XU | WX X → aba | VX

Can you please help me with this question, following the steps/ instructions given in the images? As specific as possible please. Thanks. ==== Consider the CFG G2 induced by the following productions: S → aT | bV | YY T → bS | aTT U → aUV | Ub V → aS | bVV | aUY W → XU | WX X → aba | VX

Database System Concepts
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
See similar textbooks
icon
Related questions
Question

Can you please help me with this question, following the steps/ instructions given in the images? As specific as possible please. Thanks.
====

Consider the CFG G2 induced by the following productions:

S → aT | bV | YY
T → bS | aTT
U → aUV | Ub
V → aS | bVV | aUY
W → XU | WX
X → aba | VX
Y → abS | SY | ε

 

Give a grammar in Chomsky normal form that generates L(G2) \ {ε}. You must use all steps of the transformation described in the handout in the given sequence.

3. A non-terminal A is generating if A ⇒* w for some w € Σ*. * If A → w € P and w contains only terminals, A is generating. * If A → w€ P and w contains only terminals or generating non-terminals, A is generating. * Remove each non-generating non-terminal with all productions containing it. 4. A non-terminal A is reachable if S * uAv for some u, v € (EUN)*. * S is reachable. * If A → w€ P and A is reachable, every non-terminal in w is reachable. * Remove each non-reachable non-terminal with all productions containing it. 5. Consider every terminal a in a right-hand side of length at least 2. * Add a new non-terminal A and the production A → a. * Replace every occurrence of a in a right-hand side of length at least 2 with A. 6. Consider every production A → B₁ B₂ ….. Bɲ with n ≥ 3. n * Add a new non-terminal C and replace this production with A → B₁C and C → B₂B3... Bn. * Repeat this step while there are changes.
Transcribed Image Text:3. A non-terminal A is generating if A ⇒* w for some w € Σ*. * If A → w € P and w contains only terminals, A is generating. * If A → w€ P and w contains only terminals or generating non-terminals, A is generating. * Remove each non-generating non-terminal with all productions containing it. 4. A non-terminal A is reachable if S * uAv for some u, v € (EUN)*. * S is reachable. * If A → w€ P and A is reachable, every non-terminal in w is reachable. * Remove each non-reachable non-terminal with all productions containing it. 5. Consider every terminal a in a right-hand side of length at least 2. * Add a new non-terminal A and the production A → a. * Replace every occurrence of a in a right-hand side of length at least 2 with A. 6. Consider every production A → B₁ B₂ ….. Bɲ with n ≥ 3. n * Add a new non-terminal C and replace this production with A → B₁C and C → B₂B3... Bn. * Repeat this step while there are changes.
A CFG G = (N, E, P, S) is in Chomsky normal form if every production has the form * A → BC, where B, C € N, or *Aa, where a € E. * The right-hand side of each production is either two non-terminals or a terminal. For every CFG G with & L(G) there is a CFG G' in Chomsky normal form with L(G) = L(G'). 1. Eliminate ɛ-productions of the form A → ɛ. 2. Eliminate unit-productions of the form A → B. 3. Eliminate non-generating non-terminals. 4. Eliminate non-reachable non-terminals. 5. Eliminate terminals from right-hand sides of length at least 2. 6. Eliminate right-hand sides of length at least 3. 1. If A → uBv € P for u, v € (ΣUN)* and B → ɛ € P, add A → uv to P. * Repeat this step while there are changes. * Afterwards, remove all ɛ-productions of the form A → ɛ. 2. If A → B EP and B → w EP for wE (UN)*, add A → w to P. * Repeat this step while there are changes. * Afterwards, remove all unit-productions of the form A → B.
Transcribed Image Text:A CFG G = (N, E, P, S) is in Chomsky normal form if every production has the form * A → BC, where B, C € N, or *Aa, where a € E. * The right-hand side of each production is either two non-terminals or a terminal. For every CFG G with & L(G) there is a CFG G' in Chomsky normal form with L(G) = L(G'). 1. Eliminate ɛ-productions of the form A → ɛ. 2. Eliminate unit-productions of the form A → B. 3. Eliminate non-generating non-terminals. 4. Eliminate non-reachable non-terminals. 5. Eliminate terminals from right-hand sides of length at least 2. 6. Eliminate right-hand sides of length at least 3. 1. If A → uBv € P for u, v € (ΣUN)* and B → ɛ € P, add A → uv to P. * Repeat this step while there are changes. * Afterwards, remove all ɛ-productions of the form A → ɛ. 2. If A → B EP and B → w EP for wE (UN)*, add A → w to P. * Repeat this step while there are changes. * Afterwards, remove all unit-productions of the form A → B.
Expert Solution
steps

Step by step

Solved in 3 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Processes of 3D Graphics
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS