Question

- Given this Grammar (we substitute one element per line)
(rules#) One substitution must be permitted by one rule
(rules#)
<S> -> a<S>c<B> | <A> | b (1,2,3)
<A> -> c<A> | c (4,5)
<B> -> d | <A> (6,7)

- Which of the following sentences are in the language generated by the Grammar ?

sentences
a- abcd
b- acccbd
c- acccbcc
d- acd
e- accc

(accc sentence can be left_derived by using some grammar rules) :
The e- Solution is given here as a successful left Derivation:

Try to derive more from the given sentences.

(rule#)
<S> -> a <S> c <B> (1)
-> a <A> c <B> (2)
a <A> c <A> (7)
a c c <A> (5)

-> a c c c (5)

A successful derivation leads to terminals only;
Compilers approve <accc> this given language syntax that is defined by this given grammar.

Answer 1

The production rules are as follows

<S> -> a <S> c <B> | <A> | b (1, 2, 3)
<A> -> c <A> | c (4, 5)
<B> -> d | <A> (6, 7)

(a) abcd

<S> -> a <S> c <B> (1)

-> a b c <B> (3)

-> a b c d   (6)

(b) acccbd

It cannot be derived from the given production rules as shown below

<S> -> a <S> c <B> (1)

Now we try to generate the three c's using the sentential form given below

-> a <A> c <B> (2)

We can know see that we cannot generate 'b' as <S> is lost and cannot be re-generated.

Hence, the given string cannot be generated.

(c) acccbcc

It cannot be derived from the given production rules as shown below

<S> -> a <S> c <B> (1)

Now we try to generate the sentential form given below for generating three c's after 'a'

-> a <A> c <B> (2)

We can know see that we cannot generate 'b' as <S> is lost and cannot be re-generated.

Hence, the given string cannot be generated.

(d) acd

It cannot be derived from the given production rules as ε epsilon (ε is epsilon used to represent null string. In some books null string is also denoted by λ (lambda) ) is not generated by <S>. The smallest length string that can be generated is "a b c d".

(e) accc

<S>  -> a <S> c <B> (1)

-> a <A> c <B> (2)

-> a <A> c <A> (7)

-> a c c <A> (5)

-> a c c c   (5)

Hence only the sentences in part (a) and (e) are there in the given language.