MathB.in - Share Mathematics with LaTeX and Markdown

The Chomsky normal form for $L$ consists exclusively of rules of the form:

$A\to BC$ and $A\to a$, $S\to \epsilon$, for nonterminal symbols $A$, $B$, and $C$, and terminal symbol $a$, and so that $S$ does not occur on the right hand side.

The idea now is to construct a list of rules that keep track of the left and right parts of a word. So generate a new set of rules, by first relabeling the starting symbol to $S_0$ instead of $S$, and adding a trivial rule, $S_0\to\epsilon$, and for each rule of the form $A\to a$, add a new rule of the form $A_0\to a$. Then for each rule of the form $A\to BC$, augment the rule set with two new rules, $A_0\to BC_0$, and $A_0\to B_0$. Now it is impossible to have an unmarked symbol (e.g. $A$) on the right hand side of a marked symbol (e.g. $A_0$) anywhere in the derivation chain. Additionally, this language is in fact the prefix language, since any word in the final output must now be missing characters only on the right of some fixed point (marked by the point where the characters change from unmarked to marked).

Observe that the new rules conform to the Chomsky normal form, therefore, the prefix language is context-free.

b) It is possible to do the same construction as above with two types of markers to recognise the midrange language, but the construction is tedious. Just take my word for it.

Wed, 08 Apr 2020 16:34 GMT