For the Context-Free Parsing, question 2, why there is no CFG? CFG should handle well-formed parentheses well. I understand that CFG can't accept interleaved form (a^n b^m c^n d^m), but for the case in the exam, it should be able to accept the string (a^n b^m c^m d^n) like:
@Anonymous: crap :)... I thought I wrote the question the other way (the one that is impossible) and didn't bother actually trying to solve it! You're absolutely right. We'll give points back on that one :).
For the Context-Free Parsing, question 2, why there is no CFG? CFG should handle well-formed parentheses well. I understand that CFG can't accept interleaved form (a^n b^m c^n d^m), but for the case in the exam, it should be able to accept the string (a^n b^m c^m d^n) like:
ReplyDeleteS->X
X->a X d
x->a d
X->Y
Y->b Y c
Y->b c
@Anonymous: crap :)... I thought I wrote the question the other way (the one that is impossible) and didn't bother actually trying to solve it! You're absolutely right. We'll give points back on that one :).
ReplyDelete(This is why I like to post solutions....)
Or with only four productions :-P
ReplyDeleteS -> aSd | M
M -> bMc | ε