New answers tagged

1

Let $L$ be a unary context-free language. According to the pumping lemma, there is a constant $p$ such that if $a^n \in L$ then either $n < p$ or there exists $q \in \{1,\ldots,p\}$ such that $a^{n+tq} \in L$ for all $t \geq 0$ (actually, the pumping lemma gives $t \geq -1$). Let $L_0$ be the set of words in $L$ of length smaller than $p$, and for $q \in \...


2

Starting point: $$ S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b $$ Substitute values of $A,B,E$: $$ S \to aCD \\ C \to bD \mid \varepsilon \\ D \to C \mid b $$ Substitute values of $D$: $$ S \to aCC \mid aCb \\ C \to bC \mid bb \mid \varepsilon $$ You can generate $bb$ from $C$ even without the rule $C \...


2

I think you can solve this using this construct: $$S \rightarrow ASA|BSB|ATA|BTB $$ $$T \rightarrow CAZC|CBZC$$ $$Z \rightarrow AZ|BZ|\epsilon$$ $$A \rightarrow a , B \rightarrow b, C \rightarrow c$$ First rule provides the $w$ and $w^R$ in the language, second rule makes sure $v \ge 1$ and has 1 c in both sides and third is just constructing the $v$ ...


1

I see two flaws in this proof sketch, one related to CFLs vs CFGs, and another related to nested quantifiers and running time as a function of multiple parameters. Any time you have a high-level proof strategy that seems to lead to surprising results, it is a good idea to check it carefully by expanding each step to obtain a detailed proof. Expand each ...


0

This language is not CFL. Consider the language $L \cap a^*b^*c^*$ . Assume that $L$ is CFL, now, as $ a^*b^*c^*$ is regular and CFL are closed under intersection with regular languages, $L \cap a^*b^*c^*$ would be CFL. But $L \cap a^*b^*c^* = a^nb^nc^{2n}$, which is not context free (The proof is similar to this). Hence the contradiction! Thus the given ...


0

Your CFG looks correct, but it can be made simpler. The production $S \rightarrow SAbAbAbAS$ can be replaced by $S \rightarrow SbAbAbA$ (i.e. remove the first $A$ and last $S$) . Given any string containing $3k$ $b$'s $(k \ge 1)$, the suffix of the string starting with the third $b$ from the right can be generated by the $bAbAbA$ part. For example, if ...


1

In both languages, each string must have twice as many $a$'s as $b$'s. For a string to be in the first language, it must satisfy the additional condition that all the $a$'s occur before any of the $b$'s. So $aba$ does not belong to the first language and does belong to the second language.


1

The usual definition is that $n_a(w)$ refers to the number of $a$s in $w$. Based on this definition, $L_1$ consists exactly of words that begin with an even number of $a$s followed by half as many $b$s (no $c$s are permitted). Therefore, you have $\varepsilon, aab, aaaabb, aaaaaabbb,... \in L_1$. Whereas $L_2$ consists of words containing an even number of ...


1

Here $L$ is DCFL. (a) $f_1(L) = \{u\in\Sigma^*: ua\in L\text{ for some }a\in\Sigma\}$ (that is, $f_1(L)$ is the set of strings obtained by dropping the last symbol of strings in $L$.) Let's define homomorphism $h$ as follow: $h(a) = a, \space a\in\Sigma$ $h(\epsilon)= c$ $L' = h^{-1}(L) \cap (\Sigma^*c\Sigma), c\notin\Sigma$. (note that $L'$ is DCFL.) ...


0

$$ \begin{align*} S \to & AbBC \mid AbBCc \mid AbBCcc \; \mid \\ & aAbBC \mid aAbBCc \mid aAbbBCcc \; \mid \\ & aaAbBC \mid aaAbbBCc \mid aaAbbBCcc \\ B \to & bB \mid \epsilon \\ A \to & aaaAb \mid \epsilon \\ C \to & bCccc \mid \epsilon \end{align*} $$ The intuition is as follows: The nonterminal $B$ encodes the fact that we ...


7

Consider the language of words with the same number of a's and b's. It is non-regular but the set of prefixes is the set of all words which clearly is regular.


1

Answer to the last question of the update. The grammar $S \to aSb + 1$ is linear, but it generates the nonregular language $\{a^nb^n \mid n \geqslant 0\}$. Therefore, it cannot be converted into a regular linear grammar.


2

We say that $\alpha \Rightarrow^* \beta$ if $\beta$ can be derived from $\alpha$ in zero or more steps. (More fancily, $\Rightarrow^*$ is the reflexive-transitive closure of $\Rightarrow$.) In particular, it is always that case that $\alpha \Rightarrow^* \alpha$, for every $\alpha$, due to a derivation of zero steps. In contrast, in your case it doesn't ...


Top 50 recent answers are included