0

I'm struggling to understand how to construct a context-free grammar for the following language.

$\{b^nw|w∈\{a,b\}^∗,|w|=n,n≥0\}$

The thing that is confusing me is the beginning of the statement. I would understand a statement like the one below to mean $b$ can be the letter $(a,b)$.

$\{b^n ∈\{a,b\}^*\}$

However I don't understand how to interpret something like the following.

$\{b^nw|w∈\{a,b\}^*\}$

What is $w$ and what is $b$? How would I convert this to a context-free grammar?

Jose Arnaldo Bebita Dris
  • 1
confusedman
  • 1
  • 1
    $w \in {a, b}^*$, that is $w$ can be either empty or composed of letters $a$ and/or $b$. $b^n$ is just a word that contains only $b$ repeated $n$-times – valuemis Jul 06 '21 at 22:58
  • So does this mean that because $b^nw$ and has the following constraint $|w|=n$. Can the string only be empty or a series of consecutive $b$'s? @valuemis – confusedman Jul 06 '21 at 23:06
  • The words of given language can be e.g.: $\varepsilon$, $ba$, $bb$, $bbaa$, $bbab$.. – valuemis Jul 06 '21 at 23:09
  • "$|w| = n$" means the length of $w$ is $n$. This words in this grammar are, for each choice of nonnegative $n$, $n$ copies of $b$ concatenated with any length $n$ word in $a$ and $b$. – Eric Towers Jul 06 '21 at 23:10

2 Answers2

1

For the given language, we can put out some words:
$\varepsilon, ba, bb, bbaa, bbab$..

That is, length of the word is $2n$.

Notice that the first half of the word is consisted only of $b$'s of length $n$, the other half is consisted of $\{a, b\}^*$, that is either empty word ($\varepsilon$) (iff $n = 0$) or a mixture of $a$'s and/or $b$'s.
Let us construct the production rules: $$S \rightarrow W | E$$ $$W \rightarrow bWa | bWb | ba | bb$$ $$E \rightarrow \varepsilon$$

Do not forget to construct the grammar as a tuple of 4, defined here.

valuemis
  • 156
0

Your language can be generated by the grammar $$ S \to bSa + bSb + 1 $$ where $1$ denotes the empty word. Can you see why?

J.-E. Pin
  • 40,163