People who code: we want your input. Take the Survey

New answers tagged

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


0

In what regard do these algorithms differ exactly? In both u mark first the atomic formula / terminal rules, and then use the exact same strategy to further mark subformulas/ rules. Sry for reopening the question but I can't find an answer myself to it.


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


0

In your first grammar, change S to X and leave A unchanged. In your second grammar, change S to Y and A to B. Then add S -> X | Y. And fix your grammars to handle n < m-1 instead of n=m-2 and n>m-1 instead of n = m+2.


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


-1

A quick google search gave me this. The definition 2 seems to be what you want.


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'= (\...


0

If the question is really about $w \in \{ a, b \}$ (i.e., $w$ is an $a$ or a $b$), a grammar would be: $\begin{align*} S &\to a A a \mid b B a \\ A &\to a A a \mid a c a \\ B &\to b B a \mid a c a \end{align*}$


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.


0

One way to approach this question is to prove the equivalent statement: $$G^\prime \text{ ambiguous} \implies G \text{ ambiguous}$$ This statement is called the contrapositive of the original statement. Now you can use the definition of ambiguity of a Grammar (which happens to be in CNF in your case) and work your way to proving the ambiguity of the original ...


0

The problem is not very hard if you break the proof of the pumped string not being in the language into cases. So let's work this out. $$L = \{\omega \omega^Ra^{|\omega|}\;| \; \omega\in \{a,b\}^*\}$$ For every $n$, let us consider the string $\omega = a^nb^nb^na^na^{2n}$. You can check that this does belong to the language. We are supposed to show that for ...


0

It is not context free. I.e., it is illegal to call a function that isn't defined, and that can't be expressed by a context free grammar. Or just write print(a) at your nearest Python interpreter, it will inform you a isn't defined.


-1

Take the language $L = \{a^{n^2} \colon n \ge 1\}$, it is easy to prove non-regular (and non-context-free). However, $L^*$ is the language denoted by $a^*$, which is regular (and thus context free).


0

The idea is that a word $uvw\in L$ can be written as $x\alpha y\beta z$ with $x, y, z \in \{0,1\}^*$, $\alpha, \beta\in \{0,1\}$, verifying the following conditions: $\alpha \neq \beta$ $|x\alpha z| = |u| = |v| = |w|$. This implies $|x| + |z| + 1 = |u|$ and then $|y| = 3|u| - 2 - |x|-|z| = 2|u| - 1 = 2 |x| + 2|z| + 1$. That means that if we use a grammar ...


2

You should first construct a PDA for your grammar. You can then use the tape in stead of the stack. When pushing something in the stack, write it on the tape of the TM from left to right. When poping the stack, read the tape then move the head left if necessary. There is no other change (states and transitions can be the same).


3

You can use the pumping lemma to show that this language is not context-free. Suppose it is context-free and let $n$ be the constant of the pumping lemma. Consider the word $u = a^nb^nc^nd^{3n}$. $u$ can be written $u = vwxyz$ with: $|wxy| \leq n$ $|wy| > 0$ $\forall k \in \mathbb{N}, vw^kxy^kz\in L$. Now using the first condition, $wxy$ can be written ...


2

When $vwx = a^j b^k$, there are two possibilities: $v$ contains both $a$s and $b$s, or $x$ contains both $a$s and $b$s. In this case $uv^2wx^2y \notin a^*b^*$, and in particular $uv^2wx^2y \notin L$. $v = a^s$ and $x = b^t$, where $s,t>0$ and $s+t \leq p$ (since $|vwx| \leq p$). In this case, $uv^0wx^0y = a^{p^2-s}b^{p-t}$, and so $p^2 - s \leq (p-t)^2 \...


Top 50 recent answers are included