Convert regex to regex / right linear grammar
I want to check that I am correctly converting this regex to the correct linear grammar based on the information from this previous question and Grijesh's wonderful answer: Left-Linear and Right Linear Grammars
Here's the question: "Write a regular (right-handed linear) grammar that generates many lines denoted by the regular expression ((10) + (011 + 1) +) * (0 + 101) *."
And here are the grammars I created, with my last one at the bottom:
1:
S --> 1
0:
S --> 0
10:
S --> 1A
A --> 0
(10)+:
S --> 1A
A --> 0 | 0S
011:
S --> 0A
A --> 1B
B --> 1
(011 + 1):
S --> 0A | 1
A --> 1B
B --> 1
(011 + 1)+:
S --> 0A | 1 | 1S
A --> 1B
B --> 1 | 1S
(10)+ (011 + 1)+:
S --> 1A
A --> 0S | 0B
B --> 0C | 1 | 1B
C --> 1D
D --> 1 | 1B
((10)+ (011 + 1)+)*:
S --> 1A | ε
A --> 0S | 0B
B --> 0C | 1 | 1B
C --> 1D
D --> 1 | 1B
0:
S --> 0
101:
S --> 1A
A --> 0B
B --> 1
(0 + 101):
S --> 0 | 1A
A --> 0B
B --> 1
(0 + 101)*:
S --> 0 | 1A | ε
A --> 0B
B --> 1
((10)+ (011 + 1)+)* (0 + 101)*:
S --> 1A | ε | E
A --> 0S | 0B
B --> 0C | 1 | 1B
C --> 1D
D --> 1 | 1B | 1E
E --> 0 | 1F | ε
F --> 0G | 0E
G --> 1 | 1E
Can anyone help me check if this is correct? Thank you bundles!: D
source to share
Everything looks right:
((10)+ (011 + 1)+)*:
S --> 1A | ε
A --> 0S | 0B
B --> 0C | 1 | 1B
C --> 1D
D --> 1 | 1B
Your grammar for the inner expression is correct:
(10)+ (011 + 1)+:
S --> 1A
A --> 0S | 0B
B --> 0C | 1 | 1B
C --> 1D
D --> 1 | 1B
Note that the only difference is that you are allowing an empty string. Closing Kleene adds more than just an empty string: it lets you repeat the entire pattern. Perhaps this could be fixed by adding derivatives to the first grammar B --> 1S
and D --> 1S
thus allowing an arbitrary number of repetitions.
The same error occurs in this pair:
(0 + 101):
S --> 0 | 1A
A --> 0B
B --> 1
(0 + 101)*:
S --> 0 | 1A | ε
A --> 0B
B --> 1
The second grammar must add derivatives S --> 0S
and B --> 1S
to allow for an arbitrary number of repetitions.
The rest of the construction looks correct and along with the corrections mentioned above, there should be correct grammar.
Note. You can do it algorithmically:
- Using an Algorithm to Generate an NFA from a Regular Expression
- Using an Algorithm to Generate DFA from NFA
- (Optional) Using an algorithm to minimize DFA
- Using an algorithm to generate a regular grammar from DFA
The long pole in the computing tent is step 2; this step is not even necessary if you can eliminate epsilon / lambda transitions instead of fully defining the automaton. The reason this would be sufficient is that the process of turning DFA into a regular grammar turns states into nonterminal symbols and maps a transition f(q, s) = q'
to a work q := sq'
, and q := s
also accepts q'
. As long as the NFA has no empty transitions, you can go ahead and use that.
source to share