TITLE: Give a context-free grammar
QUESTION [0 upvotes]: 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?

REPLY [0 votes]: Your language can be generated by the grammar
$$
S \to bSa + bSb + 1
$$
where $1$ denotes the empty word. Can you see why?
{"set_name": "stack_exchange", "score": 0, "question_id": 4192154}