A left-most derivation is a derivation such that at every step, the left-most no
ID: 3554097 • Letter: A
Question
A left-most derivation is a derivation such that at every step, the left-most non-terminal symbol is chosen for expansion (to be replaced).
Example: Left-most derivation of the string: jim ate cheese
S ===> PVP By using production S ---> PVP
PVP ===> NVP . . . P ---> N
NVP ===> jimVP . . . N ---> jim
jimVP ===> jim ate P . . . V ---> ate
jim ate P ===> jim ate N . . . P ---> N
jim ate N ===> jim ate cheese . . . N ---> cheese
A right-most derivation is a derivation such that at every step, the right-most non-terminal symbol is chosen for expansion.
Example: Right-most derivation of the string: jim ate cheese
S ===> PVP By using production S ---> PVP
PVP ===> PVN . . . P ---> N
PVN ===> PV cheese . . . N ---> cheese
PV cheese ===> P ate cheese . . . V ---> ate
P ate cheese ===> N ate cheese . . . P ---> N
N ate cheese ===> jim ate cheese . . . N ---> jim
Grammar:
Set of productions: P
Explanation / Answer
a) big cheese ate jim
productions used:
a) S --> P V P
A P V P { P-->AP}
big P V P { A-->big}
big N V P { P -->N}
big cheese V P { N-->cheese}
big cheese ate P { V -->ate}
big cheese ate N { P -->N}
big cheese ate jim { N -->jim}
b) green jim ate green big jim
S -->PVP
APVP
green PVP
green N VP
green jim V P
green jim ate P
green jim ate A P
green jim ate green P
green jim ate green A P
green jim ate green big P
green jim ate green big N
green jim ate green big jim
2. Provide the right-most derivation and the parse tree of each of the following sentential forms:
a) big jim ate green cheese
S -->PVP
P V A P { P-->A P}
P V A N { P -->N}
P V A cheese { N -->cheese}
P V green cheese { A-->green}
P ate green cheese { V -->ate}
A P ate green cheese { P-->AP}
A N ate green cheese { P-->N}
A jim ate green cheese { N --> jim}
big jim ate green cheese {A -->big}
b) jim ate green big cheese
S -->PVP
PV AP
P V A AP
P V A A N
P V A A cheese
P V A big cheese
P V green big cheese
P ate green big cheese
N ate green big cheese
jim ate green big cheese
3. Is the string big ate green cheese in the language L(G1)? Justify your answer.
big ate green cheese is NOT in the language L(G1).
we start the derivation with the start symbol.
S ==> PVP
to get 'big' at the starting of the string, we need A that derives 'big'{ A==> big}
S ==> AP VP { P==>AP}
big P V P
P derives either big, cheese, jim but not 'ate'
so we will not get big followed by ate according to the grammar. so it is NOT in the language.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.