Question

Construct a right linear and left linear grammar for language L ((b*a + aa*b) *)in TOC​

Answer 1

I hope this question can help you like me follow me tattoo all comment me thank you

Answer 2

Answer:

The complete expression grammar is as follows

S→AaBa

A→Ab|b

B→Bb|b

Explanation:

Given: Regular language

To find: Construct a right linear and left linear grammar for language

Solution:

Regular grammar describes a regular language. It consists of four components, which are as follows −

$G = (N, E, P, S)$

Where,

• N − finite set of non-terminal symbols,
• E − a finite set of terminal symbols,
• P − a set of production rules, each of one is in the forms

$S \rightarrow aB\\S \rightarrow a\\S \rightarrow \epsilon,$

$S\epsilon N$ is the start symbol.

The above grammar can be of two forms −

Right Linear Regular Grammar

Left Linear Regular Grammar

Linear Grammar

When the right side of the Grammar part has only one terminal then it's linear else non linear.

Right linear grammar

Right linear grammar means that the non-terminal symbol will be at the right side of the production.

It is a formal grammar (N, Σ, P, S) such that all the production rules in P are of one of the following forms −

$L \rightarrow a, { L is\ a\ non-terminal\ and \a \is\ a\ terminal\ in\ \sum}\\L aM, \{L\ and\ M \are\ non-terminals\ in\ N and\ a\ is\ in \sum}\\L \rightarrow \epsilon.$

S -> aA      for writing string starting with a

A -> aA | ^ B  for writing string a*

B -> abB | aB | ^     for writing (ab + a)*

Step 2 Right - linear Grammar for the language

S -> aA

A -> aA | ^ B

B -> abB | aB | ^

Rules used

+-------------------------------+--------------------+------------------------+

| TYPE | REGULAR-EXPRESSION | RIGHT-LINEAR-GRAMMAR |

+-------------------------------+--------------------+------------------------+

| SINGLE TERMINAL | e | S --> e |

| UNION OPERATION | e + f | S --> e | f |

| CONCATENATION | ef | S --> eA, A --> f |

| STAR CLOSURE | e* | S --> eS | ^          

Left Grammar

The left grammar for the above right linear grammar is,

bn ⇒ A→Ab|b

bm ⇒ B→Bb|b

The complete expression grammar is as follows −

S→AaBa

A→Ab|b

B→Bb|b