Consider the following grammar: <S> ? <A> a <B> b <A> ? <A> b | b <B> ? a <B> |
ID: 3558182 • Letter: C
Question
Consider the following grammar:
<S> ? <A> a <B> b
<A> ? <A> b | b
<B> ? a <B> | a
Which of the following sentences are in the language generated by this grammar?
baab
bbbab
bbaaaaa
bbaab
Consider the following grammar:
<S> ? a <S> c <B> | <A> | b
<A> ? c <A> | c
<B> ? d | <A>
Which of the following sentences are in the language generated by this grammar?
abcd
acccbd
acccbcc
acd
accc
a.baab
b.bbbab
c.bbaaaaa
d.bbaab
Explanation / Answer
1) <A> will generate one or more consecutive b's
<B> will generate one or more consecutive a's
So <A> a <B> b will generate
One or more b's followed by One a followed by One or more a's followed by a b which is the same as
One or more b's followed by Two a's followed by a b
Which matches a and d
2) <A> generates one or more c's
<B> will generate either One d or a string of one or more c's
So S will generate
a <S> c {d | c's} | c's | b
which matches a and e
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.