0
$\begingroup$

I have stumbled across these 2 problems

  1. $L_1= \{\alpha \mid w \in \{a,b\}^* | \alpha $ has exactly 2 b's$\} $ ,prove that $L =\{ \alpha^n | \alpha ∈ L_1 ,n \ge 0 \}$ is not context free

  2. Given : $P= \{\alpha \mid w \in \{a,b,c\}^* | \alpha $ is palindrom with even length $\} $ and $L_2= \{\beta b^n| b$ ∈ $P^n$ and $n ∈ \mathbb{N} $} prove that $L_2$ is context free.

In both problems we have degree $n$ of a word with length >1,usually in such problems how do we cope with that ?Also any suggestions,tricks or hints how to proceed in these 2 problems or in general with degree $n$ will be very helpful

Improve this question
$\endgroup$
2
  • $\begingroup$ What do you mean by "degree" here? I don't think that's standard terminology. What have you tried and where did you get stuck? $\endgroup$
    – Raphael ♦
    May 31 '18 at 12:12
  • $\begingroup$ I'm closing as duplicate of our references posts as they answer your general questions. $\endgroup$
    – Raphael ♦
    May 31 '18 at 12:12