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 , b in input correspond a on stack.
  • the characters c , d correspond c on stack.
  • if stack empty or top a, , a on input, consume , push a stack.
  • if stack empty or top a, , b on input, consume , push aa stack.
  • if stack empty or top c, , c on input, consume , push cc stack.
  • if stack empty or top c, , d on input, consume , push c stack.
  • if stack top c , a on input, consume a , pop c.
  • if stack top c , b on input, consume b , pop c, moving special state either pop c or pushes a if 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

Popular posts from this blog

user interface - How to replace the Python logo in a Tkinter-based Python GUI app? -

objective c - Greedy NSProgressIndicator Allocation -

how to set an OCR language in Google Drive -