CODEWITHSUNDEEP
automataambiguous-grammar
Fulla
Fulla

Reputation: 77

Find a s-grammar (simple grammar)

find a simple grammar (a.k.a s-grammar) for the following language:

L={(ab)2mb :m>=0}

[i did this but it is wrong]

S-> aASBB|b

A-> a

B->b

Upvotes: -2

Views: 1358

Answers (2)

Aaron
Aaron

Reputation: 1

How about S->aAb|b A->aAb|bB B->lambda

Upvotes: 0

Patrick87
Patrick87

Reputation: 28312

What about this?

S -> aA | T
A -> bB
B -> aC
C -> bS
T -> b

This is a regular grammar - all productions of the form X -> sY or X -> t, and corresponds to a minimal DFA for the language in question via a direct mapping of productions to transactions and nonterminal symbols to states.

Upvotes: 1

Related Questions