A non-terminal A is reachable if S ⇒ uAv for some u, v E (UN)*. That is: . S is reachable. • If A WEP and A is reachable, then every non-terminal in w is reachable. Write a function reachable_nts (cfg_str) that returns a set containing all the reachable non-terminals in the given CFG, where cfg_str is a multi-line string representing a CFG in the format described in the info panel before Question 6. Notes: • Study the examples below carefully. Make sure you understand why each non-terminal is or is not reachable. • Your answer may contain helper functions. • You may find it convenient to use the helper function provided in the answer box to convert cfg_str into a dictionary. However, you are also welcome to discard it and write your own code for processing cfg_str. • The string method str.isupper may be useful for identifying non-terminals. (Remember that terminals may be numeric, so str.islower is probably not useful for identifying terminals.) For example: Test # The CFG G1 above, in which all NTs are reachable. cfg="""S=BA A=a|BA|BB B=b|AA""" print (sorted (reachable_nts (cfg))) Result ['A', 'B', 'S'] # C looks reachable at first but isn't. Can you see why? cfg=""S=aB | bA A=aS | bAA B=bS | aBB |_ C=abc|SC""" print (sorted (reachable_nts (cfg))) # A tricky case: S is not in any productions but still reachable. ['S'] # By definition, S is reachable from S using 0 derivation steps # (so no productions are needed). cfg "A=0A1" print (sorted (reachable_nts (cfg))) ['A', 'B', 'S']
A non-terminal A is reachable if S ⇒ uAv for some u, v E (UN)*. That is: . S is reachable. • If A WEP and A is reachable, then every non-terminal in w is reachable. Write a function reachable_nts (cfg_str) that returns a set containing all the reachable non-terminals in the given CFG, where cfg_str is a multi-line string representing a CFG in the format described in the info panel before Question 6. Notes: • Study the examples below carefully. Make sure you understand why each non-terminal is or is not reachable. • Your answer may contain helper functions. • You may find it convenient to use the helper function provided in the answer box to convert cfg_str into a dictionary. However, you are also welcome to discard it and write your own code for processing cfg_str. • The string method str.isupper may be useful for identifying non-terminals. (Remember that terminals may be numeric, so str.islower is probably not useful for identifying terminals.) For example: Test # The CFG G1 above, in which all NTs are reachable. cfg="""S=BA A=a|BA|BB B=b|AA""" print (sorted (reachable_nts (cfg))) Result ['A', 'B', 'S'] # C looks reachable at first but isn't. Can you see why? cfg=""S=aB | bA A=aS | bAA B=bS | aBB |_ C=abc|SC""" print (sorted (reachable_nts (cfg))) # A tricky case: S is not in any productions but still reachable. ['S'] # By definition, S is reachable from S using 0 derivation steps # (so no productions are needed). cfg "A=0A1" print (sorted (reachable_nts (cfg))) ['A', 'B', 'S']
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
Related questions
Question
def cfg_str_to_dict(cfg_str):
"""Converts a multiline CFG string representation
of the form used in COSC261 quiz questions
into a dictionary represention, e.g.
"S=ab|bA|BB|_" becomes {"S": ["ab", "bA", "BB", ""]}
"""
nonterminals = {char for char in cfg_str if char.isupper()}.union({'S'})
result = {nt: [] for nt in nonterminals}
productions = cfg_str.splitlines()
for production in productions:
nt, rhs = production.split("=")
rhs = rhs.replace("_", "") # Use "" for epsilon
rhs_list = rhs.split("|")
result[nt] = result.get(nt) + rhs_list
return result
![A
non-terminal A is reachable if S ⇒* uAv for some u, v E (UN)*. That is:
. S is reachable.
• If A w EP and A is reachable, then every non-terminal in wis reachable.
Write a function reachable_nts (cfg_str) that returns a set containing all the reachable non-terminals in the given CFG, where cfg_str is a multi-line string
representing a CFG in the format described in the info panel before Question 6.
Notes:
Study the examples below carefully. Make sure you understand why each non-terminal is or is not reachable.
• Your answer may contain helper functions.
• You may find it convenient to use the helper function provided in the answer box to convert cfg_str into a dictionary. However, you are also welcome to discard it
and write your own code for processing cfg_str.
• The string method str.isupper may be useful for identifying non-terminals. (Remember that terminals may be numeric, so str.islower is probably not useful
for identifying terminals.)
For example:
Test
# The CFG G1 above, in which all NTs are reachable.
cfg = """S=BA
A=a|BA|BB
B=b|AA"""
print (sorted (reachable_nts (cfg)))
# C looks reachable at first but isn't. Can you see why?
cfg = """S=aB | bA
A=aS | bAA
Result
cfg = "A=0A1"
print (sorted (reachable_nts (cfg)))
['A', 'B', 'S']
['A', 'B', 'S']
B=bS | aBB |_
C=abc|SC"""""
print (sorted (reachable_nts (cfg)))
# A tricky case: S is not in any productions but still reachable. ['S']
# By definition, S is reachable from S using 0 derivation steps
# (so no productions are needed).](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F09c2f836-a777-444b-9271-94b360db7692%2F786e537c-c13f-4ed5-a8d8-a01c0c836c02%2Fk7fk3rh_processed.png&w=3840&q=75)
Transcribed Image Text:A
non-terminal A is reachable if S ⇒* uAv for some u, v E (UN)*. That is:
. S is reachable.
• If A w EP and A is reachable, then every non-terminal in wis reachable.
Write a function reachable_nts (cfg_str) that returns a set containing all the reachable non-terminals in the given CFG, where cfg_str is a multi-line string
representing a CFG in the format described in the info panel before Question 6.
Notes:
Study the examples below carefully. Make sure you understand why each non-terminal is or is not reachable.
• Your answer may contain helper functions.
• You may find it convenient to use the helper function provided in the answer box to convert cfg_str into a dictionary. However, you are also welcome to discard it
and write your own code for processing cfg_str.
• The string method str.isupper may be useful for identifying non-terminals. (Remember that terminals may be numeric, so str.islower is probably not useful
for identifying terminals.)
For example:
Test
# The CFG G1 above, in which all NTs are reachable.
cfg = """S=BA
A=a|BA|BB
B=b|AA"""
print (sorted (reachable_nts (cfg)))
# C looks reachable at first but isn't. Can you see why?
cfg = """S=aB | bA
A=aS | bAA
Result
cfg = "A=0A1"
print (sorted (reachable_nts (cfg)))
['A', 'B', 'S']
['A', 'B', 'S']
B=bS | aBB |_
C=abc|SC"""""
print (sorted (reachable_nts (cfg)))
# A tricky case: S is not in any productions but still reachable. ['S']
# By definition, S is reachable from S using 0 derivation steps
# (so no productions are needed).
Expert Solution

This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images

Knowledge Booster
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
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education

Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON

Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON

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)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON

Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON

C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON

Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning

Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education