HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Regular Expression as basis for creating this grammar

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
expressionthisbasiscreatingregulargrammarfor

Problem

I made a right-linear grammar from a regular expression:

The alphabet is:

$Σ = \{a, b, c\} $

Regular expression:

$r = cc^{}(ba)^{}bb$

My solution, it seems a little too short like I'm leaving something out. Maybe someone can see where I went wrong on the right-linearity:

$ S \to cA $

$ A \to b a A | B | cA $

$ B \to bb $

Solution

$A \rightarrow ba \mid A \mid B \mid cA$

under this $bababaccc$ is also legal

You could try something like this...

$S \rightarrow cS|cA$

$A \rightarrow baA|B$

$B \rightarrow bb$

Context

StackExchange Computer Science Q#14849, answer score: 3

Revisions (0)

No revisions yet.