2.19
Let CFG G be
S → aSb | bY | Ya
Y → bY | aY | ε
Give a simple description of L(G) in English. Use that description to give a CFG for L(G)c, the complement of L(G).
Solution.
I don't know the exact solution. Here I am discussing what I am thinking.
Clearly, Y generates all strings over a,b. So if we consider only last two rules for S those are bY| Ya, then they will generate all strings { w | w has length at least 1 and w either starts with a 'b' or ends with
a 'a' }. That means these two rule will not generate a string starting with a and ending with b. Now consider S → aSb. This rule generates string starting with a, ending with b and middle will not contain a string ba.
Hence L(G) have every string over a,b but not the strings of even length whose middle(center) have 'ab'. Like it will never generate <substring of length k>ab<substring of length k>.
So its complement will have all strings which look like <substring of length k>ab<substring of length k>.
S → aSb | bSa | aSa | bSb | ba
I expect it to be right, but in case I am not then please comment.
Let CFG G be
S → aSb | bY | Ya
Y → bY | aY | ε
Give a simple description of L(G) in English. Use that description to give a CFG for L(G)c, the complement of L(G).
Solution.
I don't know the exact solution. Here I am discussing what I am thinking.
Clearly, Y generates all strings over a,b. So if we consider only last two rules for S those are bY| Ya, then they will generate all strings { w | w has length at least 1 and w either starts with a 'b' or ends with
a 'a' }. That means these two rule will not generate a string starting with a and ending with b. Now consider S → aSb. This rule generates string starting with a, ending with b and middle will not contain a string ba.
Hence L(G) have every string over a,b but not the strings of even length whose middle(center) have 'ab'. Like it will never generate <substring of length k>ab<substring of length k>.
So its complement will have all strings which look like <substring of length k>ab<substring of length k>.
S → aSb | bSa | aSa | bSb | ba
I expect it to be right, but in case I am not then please comment.
I believe you are incorrect. I'll create a string ab to illustrate this:
ReplyDeleteS, Ya, aYa, aaYa, aabYa, aaba.
This string contradicts the rules you created.
I believe you are incorrect. I'll create a string ab to illustrate this:
ReplyDeleteS, Ya, aYa, aaYa, aabYa, aaba.
This string contradicts the rules you created.
You are right Derek. If I am not wrong then G can generate any string. Right?
ReplyDeleteI believe that the strings generated are all strings w where w = xyz and k >= 0 where x is k a’s, z is k b’s, and y is any string that starts with ‘b’ or ends with ‘a’...
ReplyDeleteBasically all strings that start with b or end with a sandwiched between a^k b^k
I agree with L(G) is the Unknowns. I think grammar of its complement:
ReplyDeleteS -> aSb | aY | Yb
Y -> bY | aY | ε