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
Post a Comment