3
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ "What can be say about [its] grammar?" -- note that there are many grammars for each language. Where does your claim come from? Have you tried proving it? Do you know the proof for the fact that NFA and regular grammars describe the same languages? Do you know what Greibach normal form is? $\endgroup$ – Raphael Jan 11 '16 at 7:32
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Did you mean that every regular language can be defined by set of rules built over $V = \{A, B\}$? $\endgroup$ – johni Jan 10 '16 at 20:11
  • $\begingroup$ Btw, I couldn't find anything regarding GNF saying that Regular languages can be defined by production rules of the form: $A \rightarrow \sigma B$ (only one variable). I found that there could be one or more variables, not explicitly one. Which in that case I don't see why this works for Regular languages. $\endgroup$ – johni Jan 10 '16 at 20:31
  • $\begingroup$ @johni, they're called right-linear grammars (or left-linear for the variable-on-the-left case). The set of variables can have more than two variables in it, you just only get to one on each side of the production. $\endgroup$ – Luke Mathieson Jan 11 '16 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.