0

Describe this language that is generated by a Context Free Grammar

$S \to SS$

$S \to XXX$

$X \to aX \mid Xa \mid b$

Ken
  • 3,751
Bob
  • 323

1 Answers1

0

Let's work backward. $X$ can generate any number of $a$'s with exactly one $b$ hidden in between. $S\to XXX$ turns every single $S$ into three $X$'s. $S\to SS$ generates any (positive) number of $S$'s.

Do the remaining math yourself.

Hendrik Jan
  • 1,910