retagged by
357 views
1 votes
1 votes
L = { w | w $\epsilon$ (a,b)* and #a(w) - #b(w) $\leq$ 10}. Is L regular or a CFL?
retagged by

1 Answer

Best answer
4 votes
4 votes
L = { w | w ϵ (a,b)* and #a(w) - #b(w) ≤ 10}.

number of a's - number of b's <=10. it's an infinite language because there can be infinite number of a's and b's whose difference is less than 10.

for example a's=100, b's=95   or a's=10000, b's=9998  and so on..
It's an infinite language, So if it's a regular language then its complement should also be regular, as Regular languages are closed under complement operation. Suppose $L^{c}$ is the complement of L:
$L^{c}$ = { w | w ϵ (a,b)* and #a(w) - #b(w) >10}. which also a non-regular.
Hence L is a non-regular language.
selected by

Related questions

1 votes
1 votes
0 answers
1
gari asked Jan 1, 2018
584 views
Identify the language. apbqcrds | p+r=q+s
2 votes
2 votes
1 answer
2
Tuhin Dutta asked Dec 4, 2017
408 views
$L = \{ wcww^r |\ w,c\ \epsilon\ ( a + b\ )^* \}$Identify the language.
2 votes
2 votes
1 answer
3
Warlock lord asked Sep 6, 2017
278 views
1. L = { w0x | |w|,|x|>=2 and w,x $\epsilon$ (0,1)*}2. L = {w0x | |w|,|x| is even and w,x $\epsilon$ (0,1)*} PS: '0' is zero everywhere.Are these two regular?
1 votes
1 votes
1 answer
4
just_bhavana asked Jul 4, 2017
509 views
L1 = {w | length of w is odd and its middle symbol is 0, w $\epsilon$ (0,1)*}Is it regular, a CFL or a CSL?