3

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 ...


2

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 $n$ $b$'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.


Only top voted, non community-wiki answers of a minimum length are eligible