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

See similar textbooks

Related questions

Concept explainers

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).

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 4 steps with 2 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