# Tag Info

Accepted

### Repeated rules with more than three symbols for conversion to Chomskys Normal Form

Yes, if the same strings are generated the productions can be shared. The "standard" conversion does not consider such "coincidences". Note that your final result does not yet ...
• 30.4k
Accepted

### Is there a linear language $L$ such that $\overline{L} \in \texttt{Type-2} \setminus \texttt{Lin}$?

It seems you almost solved the problem in your question statement. Note that the $n\neq m$ condition makes pumping hard: one needs a trick using factorials to succeed, see Prove if $L=\{0^m1^n∣m≠n\}$...
• 30.4k
Accepted

### How to construct context-free language $L$ to prove $L′=\{x|xx∈L\}$ is not context-free?

Take a look at $$L = \{a^nb^nc^ma^mb^kc^l : n, m, k, l \geq 0\}.$$ Now take some $x \in L$ with $x = ww$, then $x = a^nb^nc^ma^mb^kc^l$ for some $n, m, k, l \geq 0$. There's only one possible way to ...
• 630
Accepted

• 30.4k
1 vote

### Trouble proving this is regular

Note that for two ternary numbers $x = x_1x_2...x_n$ and $y = y_1y_2...y_n$ with digits $x_i$ and $y_i$ holds that $$x < y \iff x_1x_2...x_n \prec y_1y_2...y_n$$ where $\prec$ is supposed to be the ...
• 630

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