In each case find a CFG generating the given language The se

In each case, find a CFG generating the given language.

The set of odd-length strings in {a, b}* with middle symbol a.

The set of odd-length strings in {a, b}* whose first, middle and last symbols are all the same.

In each case, find a CFG generating the given language.

a. The set of odd-length strings in {a, b}* with middle symbol a.

b. The set of odd-length strings in {a, b}* whose first, middle and last symbols are all the same.

Solution

Answer:

1 . a)

S aSa | aSb | bSa | bSb | a

1. b)

S->aXa | bYb

X-> aXa | aXb | bXa | bXb | a Y-> aYa | aYb | bYa | bYb | b