principleModerate
Grammar of regular languages vs. context free languages
Viewed 0 times
freelanguagesregulargrammarcontext
Problem
Let $L$ be some language.
What could you say about $L$'s grammar if it is a regular language, that couldn't be said if it was a context free language?
For example, in case $L$ is regular,
could you say that there exists a context-free grammar $S$ such that every derivation rule of $S$ is of the form:
$$V \rightarrow \sigma_1 \sigma_2 \cdots \sigma_k V_1V_2 \cdots V_m$$
In other words, the prefix of the rule contains only symbols of $\Sigma$ and the postfix contains only variables of $V$.
What could you say about $L$'s grammar if it is a regular language, that couldn't be said if it was a context free language?
For example, in case $L$ is regular,
could you say that there exists a context-free grammar $S$ such that every derivation rule of $S$ is of the form:
$$V \rightarrow \sigma_1 \sigma_2 \cdots \sigma_k V_1V_2 \cdots V_m$$
In other words, the prefix of the rule contains only symbols of $\Sigma$ and the postfix contains only variables of $V$.
Solution
If the language is regular, then it can be defined using rules of the form $A \to \sigma B$ and $A\to \varepsilon$ by just simulating a finite state automaton. Here the nonterminals $A,B$ represent states of the automaton, and a production of the first type corresponds to a transition from $p$ to $q$ with label $\sigma$. The latter type of productions is for a final state $A$. Thus, when we use this construction the number of variables equals the number of states. As we know this number cannot be bounded.
Grammars of this type are called right-linear. Nowadays they are sometimes called regular grammars (but I am not fond of this as I would prefer regular to distinguish the expressions of that name).
If you do not like $\varepsilon$-production then we can take productions $A\to \sigma$ for transitions leading into a final state. But in this way we cannot produce the empty string.
Every context-free language can be generated by rules of the form $A \to \sigma B_1\cdots B_m$. This is called Greibach normal form. In general we can restrict to $m\le 2$ for this normal form. Restricting to $m\le 1$ will (of course) give only regular languages.
Greibach normal form is special as in each derivation step a letter is produced.
Grammars of this type are called right-linear. Nowadays they are sometimes called regular grammars (but I am not fond of this as I would prefer regular to distinguish the expressions of that name).
If you do not like $\varepsilon$-production then we can take productions $A\to \sigma$ for transitions leading into a final state. But in this way we cannot produce the empty string.
Every context-free language can be generated by rules of the form $A \to \sigma B_1\cdots B_m$. This is called Greibach normal form. In general we can restrict to $m\le 2$ for this normal form. Restricting to $m\le 1$ will (of course) give only regular languages.
Greibach normal form is special as in each derivation step a letter is produced.
Context
StackExchange Computer Science Q#51699, answer score: 11
Revisions (0)
No revisions yet.