formal languages - Context-sensitive grammar -


i'm looking context-sensitive grammar describes following language:

l = { ww | w ∈ {a,b}*, |w| ≥ 1} <br> 

i've got problems fact no rules such x -> ε allowed , therefore can't place nonterminal indicating "middle" of word. there trick problem?
if happen know answer, please help.

sure, easy. in context-sensitive grammar, can have strings on lhs; that's context. let's end string this:

abababwababab 

alright, don't want rule like

w := -empty- 

excellent. how these rules?

awa := aa awb := ab bwa := ba bwb := bb 

of course, implies should avoid introducing w unless you're sure you're going have non-empty string.


Comments

Popular posts from this blog

php - Calling a template part from a post -

Firefox SVG shape not printing when it has stroke -

How to mention the localhost in android -