5 votes
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 ...
Hendrik Jan's user avatar
  • 30.4k
3 votes
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\}$...
Hendrik Jan's user avatar
  • 30.4k
2 votes
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 ...
Knogger's user avatar
  • 630
2 votes
Accepted

Context free grammar for $L=\{a^nb^m : 2m<n<4m\}$

The problem with your (new) solution is that you force $n$ to be equal to $3m$. That means that your grammar generates words that are in $L = \{a^nb^m\mid 2m < n < 4m\}$, but words in $L$ like $...
Nathaniel's user avatar
  • 13.9k
1 vote

Context free grammar for $L=\{a^nb^m : 2m<n<4m\}$

No. The grammar you propose is not correct. For example it generates $\varepsilon$, which is not in the language. In fact, no word generated by your grammar is in the language. To see this notice that ...
Steven's user avatar
  • 29.4k
1 vote

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

Context-free languages are not closed under intersection. We start there. The relevant example is here that $\{ a^p b^p c^q \mid p,q\ge 0 \} \cap \{ a^p b^q c^q \mid p,q\ge 0 \} = K$, where $K = \{ a^...
Hendrik Jan's user avatar
  • 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 ...
Knogger's user avatar
  • 630

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