Question

Q6: (15 points) Give context-free grammar that generate the following language. a) abick ij,k 20 and i 2j +k} b) {w E 0,1' | the length of w is even, started by 1 and ended 01}

Answer 1

a) { aⁱb^jc^k | i, j, k ≥ 0 and i = 2j + k }

The language contains strings like: ε, ac, aab, aacc, aaabc, aaaccc, aaaabcc, ...

The context free grammar shown below can generate the above language.

S --> aSc / aAc / A / ε

A --> aaAb / aab / ε

For example, consider generating the word aaaabcc.

S aSc aaAcc ааaaAbcc aaaabcc

b)

{w ∈ {0, 1}^* | the length of w is even, started by 1 and ended 01}

The language contains strings like 1001, 1101, 100001, 100101, 101001, 101101, 110001, ...

Clearly, every string in this language must start with 1 and end with 01.

So,

S --> 1A01

Here, the length of the string must be an even number. The length of prefix(1) + suffix(01) is odd. So, the middle term must be a string with odd number length. So,

A --> 0T / 1T

T --> 0A / 1A / ε

S --> 1A01

A --> 0T / 1T

T --> 0A / 1A / ε

For example, consider generating the string 1010 01

S 1A01 10T01 101A01 1010T0 101001

This way, we can generate CFG's for languages.

Hope you understood the answer. Please consider commenting if you don't understand anything.