0 votes 0 votes Is the following language context free: The set of all strings with number of a’s equal to number of b’s and the sum of a’s and b’s to be divisible by 3. Theory of Computation context-free-language theory-of-computation context-free-grammar pushdown-automata + – practicalmetal asked Mar 15, 2023 practicalmetal 550 views answer comment Share Follow See 1 comment See all 1 1 comment reply ByteCode commented Jan 19 reply Follow Share We can use Pumping lemma here 0 votes 0 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes Yeah it will be context free. 1st part : Set of all strings with equal noof a's and B's is a standard CFL Language accepted by Push Down Automata. 2nd : sum of a's and B's divisible by 3 is regular language And intersection of regular language and context free language is CONTEXT FREE. Theorem : If L1 is a CFL and L2 is regular then L1 $\cap$ L2 is CFL. Proof for above : https://www.cs.umd.edu/~gasarch/COURSES/452/F14/cfgreg.pdf GNANESWARA SAI answered Mar 16, 2023 • selected Mar 16, 2023 by practicalmetal GNANESWARA SAI comment Share Follow See all 0 reply Please log in or register to add a comment.