Use the function given below to, first, help you to convert a multiline CFG string representation of the form expected into a dictionary represention. Then write the function being asked.def cfg_str_to_dict(cfg_str): """Converts a multiline CFG string representation of the form required 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 w is reachable.Write a function reachable_nts (cfg_str) that returns a set containing all the reachable non-terminals in the given CFG, wherecfg_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, youare 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, sostr.islower is probably not useful for identifying terminals.)For example:Test# The CFG G1 above, in which all NTs are reachable.cfg = """S=BAA=a | BA | BBB=b | AA"""print (sorted (reachable_nts (cfg)))# C looks reachable at first but isn't. Can you see why?cfg = """S=aB | bAA=aS | bAAB=bS | aBB |_C=abc | SC""'"print (sorted (reachable_nts(cfg)))Result['A', 'B', 'S']cfgprint (sorted (reachable_nts (cfg)))['A', 'B', 'S']# 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).= "A=0A1"

In this question we have to write a python code for the given problem statement of CFG Let's code…

Answered: Use the function given below to, first,…

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

Related questions

Question

Use the function given below to, first, help you to convert a multiline CFG string representation of the form expected into a dictionary represention. Then write the function being asked.

def cfg_str_to_dict(cfg_str):
"""Converts a multiline CFG string representation
of the form required 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 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)))
# 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)))
Result
['A', 'B', 'S']
cfg
print (sorted (reachable_nts (cfg)))
['A', 'B', 'S']
# 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).
= "A=0A1"

Expert Solution

Step by step

Solved in 3 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

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.

Similar questions