Consider the following grammar G: S → ABC|AC|A|B A → a B B - bC|a C-cD D- dA Recall that a non-terminal A is useful if there is a derivation of a string of terminals starting from S in which A appears: S=* xA y=* w holds for some x and y which are sequences of terminals and non-terminals (possibly empty) and some w which is a sequence of terminals (possibly empty). For example, if there are only three rules S→ a A, A→ B and B → a , then A is useful because S = a A=a B= a a is a derivation of the sequence of terminals a a starting from S and in which A appears. If A is not useful, then we say that it is useless. Which of the following are the useless symbols of the grammar G above?

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
icon
Related questions
Question

Hi there,

 

Can anyone please resolve the bellow question in detail step by step?

 

I want to understand why the correct answer is "None of the above". Could you please break down the process used to reach this answer? 

Consider the following grammar G:
S- ABC|AC|A|B
A - a B
B - bC|a
C-cD
D -dA
Recall that a non-terminal A is useful if there is a derivation of a string of terminals starting from S in which A appears: S =* x A y =* w
holds for some x and y which are sequences of terminals and non-terminals (possibly empty) and some w which is a sequence of terminals
(possibly empty). For example, if there are only three rules S → a A, A → B and B → a , then A is useful because S = a A = a B = a a is a
derivation of the sequence of terminals a a starting from S and in which A appears. If A is not useful, then we say that it is useless. Which
of the following are the useless symbols of the grammar G above?
O A, C, and D only
O D only
O Cand D only
A All non-terminals are useless
O None of the above
Transcribed Image Text:Consider the following grammar G: S- ABC|AC|A|B A - a B B - bC|a C-cD D -dA Recall that a non-terminal A is useful if there is a derivation of a string of terminals starting from S in which A appears: S =* x A y =* w holds for some x and y which are sequences of terminals and non-terminals (possibly empty) and some w which is a sequence of terminals (possibly empty). For example, if there are only three rules S → a A, A → B and B → a , then A is useful because S = a A = a B = a a is a derivation of the sequence of terminals a a starting from S and in which A appears. If A is not useful, then we say that it is useless. Which of the following are the useless symbols of the grammar G above? O A, C, and D only O D only O Cand D only A All non-terminals are useless O None of the above
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps with 2 images

Blurred answer
Knowledge Booster
Intelligent Machines
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