The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
108 views

Is L={1n0n0m | m+n>100} a regular language? 

asked in Theory of Computation by (93 points)
edited by | 108 views
0
I think the language is not regular as it's infinite but if the case would be m+n<100 then it would be regular.
0

I think it is a regular language because 0n0m will makes it regular

+1
L={${1^n}$ ${0^n}$ ${0^m}$} ==> {${1^n}$ ${0^{n+m}}$ ; n+m>100}

I think it is regular language...

PS:: now i think it is not regular as here no of 1's should be less than or equal to no of 0's which require comparison.
0

If we talk about complement of given Language that would be L' ={1n0n0m | m+n<=100}

Now it is regular and we know that regular is closed under regular . That why ,I think language should be regular .

0
Mishra how its complement becomes regular??
0
Since it is finite  . but please varify what i said about complement of language .
0
Its complement is {(0+1)*-L}

Exactly extracting what is L complement is little difficult..but it is definitely not like m+n<100

1 Answer

+1 vote
language which require comparison or storing of value is not regular.

its not regular as it require comparison for equality check between 1^n0^n

here no of 1's should be less than or equal to no of 0's which require comparison.

if the condition is m+n<100 in that case this will become finite hence regular.
answered by (293 points)
0

Yes you are right.

here no of 1's should be less than or equal to no of 0's which require comparison.

:)

0
@cyberscam

if the condition is m+n<100 in that case this will become finite hence regular.

How it will be regular ?..here also we r doing compariosio noe

Please suggest
0
Mayankprakash,

If m+n<100 then there is boundation, So we can find all combinations of m and n and we can draw corresponding FA
0
m+n<100  regular

m-n<100  not regular

@verma ashish  am i right?

correct me if i am wrong
0
@adarsh_1997 yes right
0
Yes m-n<100 ==> m<100+n

This is not regular

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,532 questions
54,123 answers
187,319 comments
71,044 users