CODEWITHSUNDEEP
grammarregular-languagecomputation-theory
user2364150
user2364150

Reputation: 1

Left-Linear and Right-Linear Grammar for a simple Regular Expression

I am having trouble coming up with a left-linear and right-linear grammar for the following regular expression.

0(0+1)*+10^+

I am also quite confused on what the plus-closure does.

This is what I got for the left linear grammar, but I am not sure if this is correct:

    P: S--> 0A | 1A
       A--> A0|A1|0S|0| epsilon

Thank you!

Upvotes: 0

Views: 1651

Answers (1)

templatetypedef
templatetypedef

Reputation: 372684

One general good way to find left- and right-linear grammars is to find an NFA that has the same language as your regex, then convert that NFA into a left- or right-linear grammar using the following mechanical transform:

  • For each state q, introduce a nonterminal Tq.
  • For each transition (q, r) on character a (or where a = ε), add the production Tq → aTr (for left-linear grammars) and Tr → Tqa (for right-linear grammars).

Then, for left-linear grammars:

  • For each accepting state q, add the production Tq → ε
  • For left-linear grammars with start state q0, make the start symbol the symbol Tq0.

Then, for right-linear grammars:

  • Add a start symbol S with the production S → Tq for each accepting state q.
  • Add the production Tq0 → ε for the start state q0.

Try applying this idea here and you'll end up producing left- and right-linear grammars for your language. They might not be the most efficient grammars, but they'll work.

Upvotes: 2

Related Questions