Finding a grammar for this language -
i need find context free grammar following language:
l= { w { a,b,c,d }* : #a+2#b=2#c+#d }
here attempt, doubt correct:
s -> asd|dsa|bsc|csb|absdc|bascd|dcsab|cdsba|ss|λ b -> c|dd c -> b|aa
you can construct pda recognizes language this:
- the characters
a,bin input correspondaon stack. - the characters
c,dcorrespondcon stack. - if stack empty or top
a, ,aon input, consume , pushastack. - if stack empty or top
a, ,bon input, consume , pushaastack. - if stack empty or top
c, ,con input, consume , pushccstack. - if stack empty or top
c, ,don input, consume , pushcstack. - if stack top
c,aon input, consumea, popc. - if stack top
c,bon input, consumeb, popc, moving special state either popcor pushesaif stack empty. - ...
- the accept state both input , stack empty.
that means must able construct cfg. think you're on right track, cfg going pain write since there no ordering constraints. means you'll have lot of permutations of same basic rule.
Comments
Post a Comment