Hi, I am having trouble answering the following question. Design a context-free

Question

Hi,

I am having trouble answering the following question.

Design a context-free grammar for each of the following languages. Specify the grammar 4-tuple description (i.e. G=(V,T,P,S)) in addition to providing the productions.

a) The set of all strings over alphabet {a,b} such that the number of a's is at least as many as the number of b's.

b) The set of all strings over alphabet {a,b} that are of odd length.

c) The set of all strings of a's and b's that are not of the form wwR.

Any help you can provide would be very much appreciated.

Explanation / Answer

a) The set of all strings over alphabet {a,b} such that the number of a's is at least as many as the number of b's.

a^mb^n m>=n

---------------------------

4-tuple description (i.e. G=(V,T,P,S)

V={S}

T={a,e}

P={

S---->aSb | aS | e

}

S = S

----------------------------------

e-epsilon empry string

b) The set of all strings over alphabet {a,b} that are of odd length.

-----------------------------------

4-tuple description (i.e. G=(V,T,P,S)

V={S,R}

T={a,b}

P={

S--->aR |bR |a |b

R--->aS |bS

}

S = S

------------------------------

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.