# Tag Info

Appearance checking is a concept in the theory of regulated grammars. In an ordinary (context-free) grammar we may appay a production to a string if its right-hand side occurs in that string. So for $\pi: A\to \alpha$ we write $x \Rightarrow_\pi y$ if $x= w_1 A w_2$ and $y = w_1\alpha w_2$. In a regulated grammar we may specify the order in which the ...
Consider the language $L = \{uv\mid u, v\in\Sigma^*, |u|=|v|\wedge u\neq v\}$. I claim that $L$ is context-free, it is not regular (a simple pumping lemma proof can do the trick), but $L^*$ is regular, without being equal to $\Sigma^*$, so that means that $L^*\overline{L^*}$ is regular and satisfies your conditions. Now let's show that if we denote $L'= (\... 1 It looks like the grammar indeed accepts all words of the form$[b+a]^nca^n$(which means, all words that start with any sequence of$nb$'s and$a$'s, and then a single$c$and afterward exactly$n$times the letter$a$). To show why to try to show the two following things: every word accepted by the grammar must be in such form every word with such ... 1 The idea is that$L(G) \not\subseteq \Sigma^* \setminus \{\epsilon\}$iff$\epsilon \in L(G)$. 1 Your case analysis seems right and can be used to prove non-contextfreeness. Not you don't have to find a pumping constant. To the contrary, you have to show no such constant can exist. So, the general argument is usually like "if I assume$N$is the pumping constant, I can use this word$x\in L$, longer than$N$, and whatever I try, we cannot pump it ... 1 You attack it from the exact wrong side. First, the language is the same as$\{w^m aca a^m|w\in\{a,b\},m\in\mathbb{N}\}$. For this, you apply a rule that adds$w$on the left and$a$on the right repeatedly, and then inserts$aca$in the middle and is done. By using one rule that adds both on the left and the right side, you make the number of w's and a's ... 1 You're on a good path! Keep at it. Remember that a pushdown can have a finite-state control, and you can remember up to a finite amount of information in the finite-state control. Also, it can have$\epsilon\$-transitions (so the read head doesn't consume any of the input). Those might be helpful.