1
$\begingroup$

Following is a problem that I have no idea how to solve. I'd appreciate someone showing me how to solve this problem.

A CFG is right-linear if each production body has at most one variable, and that variable is at the right end; i.e. all productions of a right-linear grammar are of form $A\rightarrow wB$ or $A\rightarrow w$, where $A$ and $B$ are variables and $w$ is some string of zero or more terminals.

  1. Show that every right-linear grammar generates a regular language. (Hint: construct an $\epsilon$-NFA simulating leftmost derivations, using its state to represent the lone variable in the current left-sentential form.)

  2. Show that every regular language has a right-linear grammar. (Hint: start with a DFA and let the variables of the grammar represent states.)

$\endgroup$
1
$\begingroup$

You have to show that for each RLIN grammar you can build a FSA for the language it represents, and vice-versa. Formally that is done by giving a construction. For a RLIN grammar $G$ explicitly give the components of equivalent automaton $\cal A$.

That is not too hard. The two formalisms are actually quite close. The production $A\to wB$ has the same effect as an automaton move $A \overset{w}\to B$. The only problem here is that in the grammar $w$ may consist of several letters, which usually is not allowed for automata.

$\endgroup$

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.