Write a BNF (or context-free) grammar for the language composed of sentences of

Question

Write a BNF (or context-free) grammar for the language composed of sentences of the following form: a2k x2j-1 b3k I.e., sentences consisting of a sequence of a's, followed by a sequence of x's of odd length, in turn followed by a sequence of b's of length exactly 3/2 as long as the sequence of a's, where k>0 and j>0. (E.g., the language includes aaaaxxxxxxxxxbbbbbb and aaxbbb but not aaxxbbb or bbxaa or abx or axxxbb.) (2 points)Part 1: Can you modify your grammar so that the resulting language is the proper subset of the original language in which j=k (thus resulting in sentences containing one fewer x's than a's)?

Explanation / Answer

This grammar will work for both PArt 1 and PArt 2, meaning that this grammar will satisfy for j not equal to k, and j equal to k, for both cases :)

    S->AXB

    A->aaA | aa | (lambda)(null)
   
    X-> xXx | x

    B-> bbbB | bbb | (lambda)(null)

Try this for when j is 7, and k is 3. Now try this for j=k=6. It will work for both :)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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