This question is on a sample exam that our professor was too lazy to type up solutions to and I am stuck pretty bad. Thanks in advance for your help!
Prove that the following language is context-free {x is an element of {a,b,c}* | the number of a's in x is greater than the number of b's or the number of c's in x}
{x is an element of {a,b,c}* | the number of a's in x is greater than the number of b's or the number of c's in x}
This can be interpreted two ways:
a's is greater than (the number of b's plus the number of c's)a's is greater than the number of b's) or (the number of a's is greater than the number of c's).Hints for 1: A PDA could work as follows. If the stack is empty and you see an a on the input, then add an a to the stack. If the stack is empty and you see a b or a c on the input, add a b to the stack. If the top-most stack symbol is a b and you see an a on the input, remove a b from the stack. If the top-most stack symbol is a b and you see a b or a c on the input, add another b to the stack. If the top-most stack symbol is an a and you see an a on the input, add another a to the stack. If the top-most stack symbol is an a and you see a b or a c on the input, remove an a from the stack. Now simply produce an argument that such a PDA will have (1) an empty stack if the number of a's is equal to the sum of the numbers of b's and c's; (2) an a on top of the stack if it saw more a's than it saw either b's or c's (combined); (3) a b on top of the stack if it saw fewer a's than it saw either b's or c's (combined).
Hints for 2: First, construct a PDA accepting any string of a's, b's, and c's which has more a's than b's, ignoring any c's (the PDA described above in Hints for 1 can be easily modified to ignore c's). Then, construct a PDA accepting any string of a's, b's, and c's which has more a's than c's, ignoring any b's (similar to the one you just built). Finally, demonstrate that the language you are trying to prove context-free is the union of the languages accepted by these automata; a simple argument should suffice. Since context-free languages are closed under union, this demonstrates the claim, i.e., that the language you set out to prove context-free is, indeed, context-free.
Please feel free to request further clarification. Also, check out the new site for questions like this: https://cs.stackexchange.com/. You might receive even better answers on future questions at that site.
The task is to show that the language can be generated by a context-free grammar.
some hints:
A -> aabAc | B
B -> B|epsilon