Example 3 Consider the synchronous rule s : The first component of a synchronous rule derived from this can be one of the following eight: The second component can be one of the following six: In total, the transformed grammar will contain 8 * 6 = 48 synchronous rules derived from s. For each synchronous rule s, the above grammar transformation produces O(|s|) left rule components and as many right rule components.
this is not possible in our case, since SCFGs do not allow normal forms with a constant bound on the length of the right-hand side of each component.