There are equivalent definitions of a type 3 grammar. One is Brian's left-linear grammar, another is that in a type 3 grammar, all the productions are of the form you listed, along with those of the form $X\rightarrow \lambda$ for some nonterminal $X$. If that's the case, you're done, so I guess you might be working with the definition that says that all productions in a type 3 grammar must be of the form
- $X\rightarrow\lambda$
- $X\rightarrow a$
- $X\rightarrow Y$
- $X\rightarrow aY$
where $X, Y$ are nonterminals and $a$ is a single terminal. In your grammar, the productions are restricted to be of the form $X\rightarrow\alpha$ and $X\rightarrow\alpha Y$, where $\alpha$ is a nonempty string of terminals.
Consider a production $X\rightarrow\alpha$ in your grammar, and let $\alpha = a_1a_2\dots a_n$, where the $a_i$ are single characters. Then, you can introduce new variables $X_1, X_2, \dots X_{n-1}$ and replace the production $X\rightarrow\alpha$ with
$$
X\rightarrow a_1X_1,\quad X_1\rightarrow a_2X_2,\quad\dots,\quad X_{n-1}\rightarrow a_n
$$
It's clear that these new productions will be equivalent to $X\rightarrow\alpha$. It's easy enouugh to see how to do the same thing to all your productions of the form $X\rightarrow\alpha Y$.
HINT: There are two slightly different definitions of Chomsky normal form. It appears that you’re using the one that simply requires each production to be of the form $X\to YZ$ or $X\to a$, rather than the one in Wikipedia; this causes no problems, since the lack of $\lambda$-productions means that $\lambda$ isn’t in the language anyway.
The algorithm given in that article for converting $G$ to $G'$ still works; we’re just in the fortunate situation of being able to ignore parts of it as not applicable. $G$ has no $\lambda$-productions or unit productions, and your definition of Chomsky normal form doesn’t require elimination of the initial symbol from the righthand side (the START step), so the last two steps, DEL and UNIT, don’t arise, and we need only perform the TERM and BIN steps.
- Show that the TERM step adds at most $|T|$ productions to the grammar.
After the TERM step has been completed, every production is of one of two kinds: $X\to a$ (where $X$ might be one of the new non-terminals introduced in the TERM step), or $X\to Y_1\ldots Y_n$, where $n\ge 2$. Productions of the form $X\to Y_1Y_2$ are fine, but we have to get rid of the ones with $n\ge 3$.
- Show that the procedure used in the BIN step replaces a production $X\to Y_1\ldots Y_n$ with $n-1$ productions of the form $Z\to UV$.
- Conclude that $G'$ has at most $|T|+(K-1)|P|$ productions.
If you were using the definition of Chomsky normal form given in the Wikipedia article, the grammar with initial symbol $S$, terminal symbols $a$ and $b$, and productions $S\to Sa\mid bb$ would be a counterexample to the theorem. Clearly $|P|=|T|=K=2$, so $(K-1)|P|+|T|=4$. However, the smallest equivalent grammar in (this version of) Chomsky normal form has six productions:
$$\begin{align*}
&S\to BB\mid XA\\
&X\to BB\mid XA\\
&A\to a\\
&B\to b
\end{align*}$$
If we allow $S$ to appear on the righthand side, we can reduce this to four, as in the theorem:
$$\begin{align*}
&S\to BB\mid SA\\
&A\to a\\
&B\to b
\end{align*}$$
Best Answer
There do indeed exist ambiguous regular grammars. Take for example
$S\rightarrow A~|~B$
$A\rightarrow a$
$B\rightarrow a$