Question
Making it CNF prep G for CYK parsing or analysis -------------------------------------------------------------------------------------------- We will start with S -> a A B b S -> e E
Making it CNF prep G for CYK parsing or analysis
--------------------------------------------------------------------------------------------
We will start with
S -> a A B b
S -> e E
A -> C C
C -> epsilon
C -> x
B -> d d
F -> f
Follow the following instructions step by step and answer each question.
You may refer to the rule numbers in answering which rules questions!
a) Remove all useless rules. [2pts]
1- Start bottom up from terminal strings.[1]
Which rules derive string?
Which rules do not derive strings and should be removed?
2- Then start top down from S.[1]
Which rules are reachable from S?
Which rules are not reachable from S and should be removed?
b) Make it epsilon-free. [4pts]
S -> a A B b
A -> C C
C -> epsilon
C -> x
B -> d d
1- Which non-terminals go directly or indirectly to epsilon (?? =*=> epsilon) [1] ?
2- Which rules use such non-terminals on the right side [1]?
3- List all the ways to make such non-terminals disappear from the right side [1].
Newly added rules are:
4- What epsilon-rules will now be removed (they go directly to epsilon)[1]?
c) Make it chain-free (no ->). [4pts]
S -> a A B b
S -> a B b
A -> C C
A -> C
C -> x
B -> d d
1- List all chain derivations (i.e. =*=> )[1]:
2- For each chain, add rule(s) to skip the right side non-terminal [1].
List added rules:
3- Delete all chain rules. List the ones to delete [1]:
4- Did any rule become useless and need to be removed? Which ones [1]?
d) Make it stratified (no non-terminal terminal mixture).[3pts]
S -> a A B b
S -> a B b
A -> C C
A -> x
C -> x
B -> d d
Add N#-> rule for each terminal (a,b,d,x) [1]
(i.e. use N1, N2, etc.):
Stratify mixed rules. [1]
Change this mixed rule:
To what?
Change this mixed rule:
To what?
Change B -> d d to what?
List the resulting grammar: [1]
(should have only one terminal or only non-terminals on the RHS)
e) Make the result of (d), binary (i.e. 2 non-terms) [2pts]
1- Change this rule:
To what?
Change this rule:
To what?
2- Final Result is:
All rules will be of the form N -> N N or N -> t
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started