in Theory of Computation edited by
1,213 views
1 vote
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?

in Theory of Computation edited by
1.2k views

4 Comments

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

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
Dfa accept all the string of Language but also reject all the string which not belong to Language
0
0

1 Answer

0 votes
0 votes
Is it regular or CFL

I think it is CFL because Finite Automata can't compare .

4 Comments

If we take -aaaaa
0
0
in 'aaaaa'..

take x= epsilon and y="aaaaa"...

na(x)=nb(y)=0
0
0
I got it x and y also may be epsilon

Thanks conceptual questions

Thanks for clearing doubt
0
0

Related questions