1 1 vote I think the below language is Regular- L = {xy | na(x) = nb(y) where x,y $\in$ (a,b)* } Doubt : Since if we consider any string in given language is split in such a way so that we satisfy the required condition. like (abbbaa)(bbaba), (bbbbb)(a) etc. (Note - brackets are just for understanding purpose). Can some one write the regular grammar for this language? Theory of Computation theory-of-computation regular-language regular-grammar + – Shubhanshu 2.2k views answer comment Share Follow Print See all 5 Comments 5 5 Comments reply joshi_nitish commented Jul 5, 2017 i edited by joshi_nitish Jul 5, 2017 reply Follow flag it will be (a+b)*...any string can be partitioned in two parts such that it satisfies above language.. 0 0 replyShare Shubhanshu commented Jul 5, 2017 reply Follow flag Yeah it is (a+b)* and its grammar will be S-> aS / bS / epsilon but how we can show that where to split? 0 0 replyShare joshi_nitish commented Jul 5, 2017 reply Follow flag i all first thought how DFA will know what is pattern for a given language because it has to see in partitions which require counting, which is not possible with a DFA....than intituinally i observe that every string can be partitioned in two parts to follow above conditions, hence it is (a+b)* 0 0 replyShare Manu Thakur commented Jul 6, 2017 reply Follow flag We don't need to show the range of partitions for each string. If a language is given, we only need to check what all strings can be accepted by its corresponding machine. DFA for this language will accept everything, So this is a regular language because we can have a dfa for it. 0 0 replyShare Nitesh Choudhary commented Jul 6, 2017 reply Follow flag Dfa accept all the string of Language but also reject all the string which not belong to Language 0 0 replyShare Please log in or register to add a comment.
0 0 votes Is it regular or CFL I think it is CFL because Finite Automata can't compare . Nitesh Choudhary answered Jul 6, 2017 Nitesh Choudhary comment Share Follow See all 6 Comments 6 6 Comments reply Show 3 previous comments Nitesh Choudhary commented Jul 6, 2017 reply Follow flag If we take -aaaaa 0 0 replyShare joshi_nitish commented Jul 6, 2017 reply Follow flag in 'aaaaa'.. take x= epsilon and y="aaaaa"... na(x)=nb(y)=0 0 0 replyShare Nitesh Choudhary commented Jul 6, 2017 reply Follow flag I got it x and y also may be epsilon Thanks conceptual questions Thanks for clearing doubt 0 0 replyShare Please log in or register to add a comment.