A CFG is said to be right-linear if each production body has at most one variabl

Question

A CFG is said to be right-linear if each production body has at most one variable, and that variable is at the right end. That is, all productions of a right-linear grammar are of the form A wB or A w, where A and B are variables and w some string of zero or more terminals.

1. Show that every right-linear grammar generates a regular language. Hint: Construct an - NFA that simulates leftmost derivations, using its state to represesnt 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.

Explanation / Answer

1)

To be proved: Right linear grammars generate regular languages.

Proof:
-------
We have to show language generated bya roght linear grammar is always regular. To do so, we
construct an nfa that mimics the derivations of a right-linear grammar. Note that the
sentinal forms of a right linear gramamr have the special form in which there is exactly
one variable and it occurs as the rightmost symbol. Suppose now that we have a step in a
derivation

ab...cD ==> ab...cdE,
arrived at by using prouction D->dE. The corresponing nfa can imitate this step by going from
state D to state E when a symbol d is encountered. In this scheme, the state of the automation
correspons to the variable in the sentinal form, while the part of the string already processe
is identical to the terminal prefix of the sentinal form. Hence proved.

2)

A grammar G=(V,T,S,P) is said to be right linear if all productions are of the form
A -> xB,
A -> x

A regular grammar is one that is either right-linear or left-linear.
Note that in a regular grammar at most one variable appears on the right sie of any prouction.
Furthermore,, that variable must consistently be either the rightmost or leftmost symbol of the
right sie of any production.

Let me explain with example:
The grammar G1 = ({s},{a,b},S,P1) with P1 given as
S -> abS|a
is right linear. The grammar G2 = ({S,S1,S2},{a,b},S,P2) with productions
  
S -> S1ab
S1 -> S1ab|S2
S2 ->a

is left-linear. Both G1 and G2 are regular grammars.
The sequence
S => abS =>ababS =>ababa
is derivation with G1. From this single instance it is easy to conjecture that L(G1) is
the language denoted by the regulat expression r = (ab)*a. Similarly L(G2) is the regular
language.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.