Regular Languages & Finite Automata (Solved Problem 1)

TOC: Regular Languages & Finite Automata (Solved Problem 1)
Topics discussed:
A solved problem form GATE 2013.
Links to topics:
1. Regular Languages: goo.gl/dXQ7fb
2. Context Free Languages: goo.gl/xDwQ7V
3. DFA to Regular Expression Conversion: goo.gl/od9uXS
4. Identities of Regular Expression: goo.gl/8oAgV3
5. Arden’s Theorem: goo.gl/d6z6RJ
6. Minimization of DFA: goo.gl/q1F3iZ
Contribute: www.nesoacademy.org/donate
Books: www.nesoacademy.org/recommended-books
Website ► www.nesoacademy.org/
Forum ► forum.nesoacademy.org/
Facebook ► goo.gl/Nt0PmB
Twitter ► nesoacademy
Pinterest ► www.pinterest.com/nesoacademy/
Music:
Axol x Alex Skrindo - You [NCS Release]
#TOCByNeso

[@AyushMo]

Option 4 - Accepting all strings of length at least 2 does not imply it cannot accept strings of length < 2. The statement isn't that 'It exclusively accepts all strings of length at least 2', it's more like 'amongst other things, it also accepts all strings of length at least 2' which it doesn't because '111' is a string of length at least 2 and isn't accepted. The option is false nevertheless, but the right counter example isn't '0' as mentioned.

[@cdm6541]

Brilliant!

[@RA-gv3ys]

Good question. Made us revise 2-3 concepts in 1. 👍🏻

[@hostelboy6744]

Complement of CFL is may or may not CFL.👍 Complement of every RL is RL👍. Every RL is CFL👍

[@akarshkumar2171]

Complement of Context free is not necessarily context free. 1st option can be proved as : Every dfa can be expressed using Reg lang (RL). The complement of RL is also regular. Every RL is context free. Hence, L(A) complement is context free.

[@sMKUMARSAISKLM]

he also told the same.

[@Shivam-eh5fc]

Sir you are doing a great job @neso academy may God bless you, I just request you to please upload videos on more subjects of computer science like CSO,DAA, computer network And please please increase the speed of uploading the video with more and more Gate questions.

[@74N]

Have my Semester Exam Tomorrow and luckily I found this today

[@jiteenmohanty2675]

same🥲

[@ashfq]

how did it go?

[@deathstroyer]

i think you misunderstood statement 4. the length atleast 2 is a requirement of the answer. so a good proof that statement 4 is false would be the string "111" which will not be accepted but is length atleast 2.

[@zoxomonocovo]

@Telugu tech solutions but is not of length at least 2

[@skzaffarekbal1820]

Lol atleast means minimum 2 length string is accepted

[@akarshkumar2171]

U misunderstood atleast with atmost. The counter example would be string {0} which is a accepted by the dfa bt the 4th statement say length less than 2 is not accepted

[@snim9515]

at 9:47 step is wrong. (0+1)* should be in common with both the terms

[@nachiketagrawal5154]

Complement of Regular language is regular. However for any general CFG, it's not closed under complement

[@nachiketagrawal5154]

3:06 : Complement of every C. F. L is also context free is incorrect

[@saimyousuf2108]

Sir please make more videos on gate questions. This was fantastic

[@zackcarl7861]

You Pakistani

[@kartikforwork]

@@zackcarl7861 how did you figure it

[@yashmane8585]

if first 2 options we get as right option, then why we check 3&4?....... that will came automatically false naa.....

[@leninsingh5264]

Bit confusing of re-arranging at 10:00. Doesn't it affect the pattern of the language?

[@derouvilleguillaume5416]

No, because there is a union (+). Let's take the final answer: 11*0 + 0 (0+1)*. In the step of the switch, he switches like this: 0 + 11*0 11*0 + 0. This remains correct because the + is a union, meaning that either the left part or the right part of the + is chosen. As he switches only the two sides of the union, the logic is unchanged here. I find that translating the regex into plain english helps. "11*0 + 0 (0+1)*" can be read as: - "11*0" is : 1, followed by 0 or more 1s, followed by 0 - 0 is: 0, self explanatory - (0+1)* is: 0 or 1, that can be found 0 or more times When reading "11*0 + 0", you need to choose one of them, to which you concatenate what is under parenthesis: (0+1)* So, the full regex can be read as: - Choose between: "1, followed by 0 or more 1s, followed by 0" OR "0" - Then, follow it with 0 or 1, that can be found 0 or more times (so nothing, or any combination of 0s and 1s)

[@10_yogeshchandrapandey90]

@nesoacademy .. Sir with all due respect, I think you have explained option 4 wrongly... Statement 4 is : A accepts all strings over {0,1} of length at least 2... But you stated as: A accepts all strings over {0,1} ONLY of length at least 2... The answer of question is still same... As string- 111 is an contradiction to statement 4.. Please correct me, if I am wrong And if got this correctly, then it is only because of you... #greatcontent thank you sir...

[@lovingtheunloved]

111 is a string of length 3 and according to DFA diagram it is not accepting it but the string 110 is getting accepted so the statement 4 is false.

[@10_yogeshchandrapandey90]

@@lovingtheunloved sorry, but I think you are not getting the point what I have said....

[@randomstuff1690]

@@10_yogeshchandrapandey90 Read the option again

[@nachiketagrawal5154]

Yes yogesh, Point 4 doesn't imply that DFA doesn't take string of length 1. He mis understood. In this case the answer didn't change but counter Example should definitely be some string of length > 2

[@proomm986]

the question said that it accepts all string at least length 2, but it can accept string with length 1 like {0} so it is false.

[@udbhavvikramsingh3449]

Instead of that much long steps For 2nd options what i did was like ////// I convert regular expression into regular language first and then i check if the DFA is accepting that regular language or not And i found DFA was accepting Is it right approach

[@vaibhavsingh4108]

yeah this was way simpler and fast method. Thanks

[@raj-nq8ke]

Nope, answer may be similar in some cases but it will not always be true

[@satyakumar-vc3zj]

in derivation of second statement i can'tunderstand on what basic you said that any thing multiplied in it there is no change please explain anyone please

[@shashwatvaibhav4596]

satya kumar because this dfa accepts the string (11*+0)(0+1)* in the final state..after that ,since the final state has a self loop on 0,1 you can add any number of 0s or 1s ...and it won't matter as the machine will be in final state itself.. that's why 0*1* was added to the right of the expression.

[@21AniketThakre]

@@shashwatvaibhav4596 Great explanation 🙌🏻

[@akashlenka4068]

@@shashwatvaibhav4596 thanks dude

[@bdjeosjfjdskskkdjdnfbdj]

How much time are you given in GATE to solve a question like this?

[@AbhishekSingh-hy4dm]

about 2 to 3 minutes considering the exam consists of 65Qs and 3hrs to solve

[@HishaMized]

17:00 It's false because it does not accept 11 {00, 01, 10, 11}? Right?

[@arjunmalli50]

Cant able understand sir

[@chimingcheng8912]

why statement 2 is true? Isn't that L(A)=L((11*0+0)(0+1)*)?

[@gatesorted6011]

+1

[@BrijeshSharma-vu3mk]

It's been 1 yr to ur comment...But still 0*1* doesn't matters at all unless it is with + to remaining language. Since it can be written as epsilon i.e empty

[@mahaveerhirawat7323]

it doesnt matter cuz (11*0+0)(0+1)* is the expression for final state. So it is in the final state now, so when u give it self loop like 0*1* it stays in the same state so we can add that there

[@sukritimacker7562]

Sir i didn't understand your answer for statement 3 For 1 equivalence you said in previous video that for certain input both the states should fall in the same set.. But here comparing A and B for input 0..A goes to C whereas B goes to B.. Where {A, B} {C} this should split

[@sukamaldash3599]

Both A and B goes to the state C for getting input 0. Try to look at the DFA again. You'll find your question wrong.

[@sukritimacker7562]

@@sukamaldash3599 okk.. Thank you.. I'll take a look

[@gauravupreti8195]

Itni pyar se kon padhata hai 🥺🥺❤️

[@KondaveetiVenugopal]

great work sir

[@siddharth.chandani]

Can anyone explain why at 10:32 , both are same ....? Acc to me, they are same..

[@mokshgrover7405]

Option 4 is incorrect ,coz it does not accept the strings of the form 11(1)*

[@subhadipde4873]

or even easier, 0 is accepted by the DFA, which is of length 0. So, it proves

[@arjunmalli50]

@mokesh I have one doubt sir why it need accept the string 11(1)* sir because in this string 11*0 one only goes to final state sir... Can you please explain sir...

[@uzaifasiddiqui3163]

Statement 2 is false since just few seconds back you proved that RE for that DFA is (11*0+0)(0+1)* ...and then within next 5 seconds you say that statement 2 is correct but it has ((11*0+0)(0+1)*0*1*).................??????????

[@10_yogeshchandrapandey90]

(0+1)* means that : all possible strings that can have combination of 0 and 1. And since 0*1* is another possible string containing 0 and 1, so it will also be accepted... Not only this string...but L(A)= (11*0+0)(0+1)*(0+1)0*.. L(A) = (11*1*1* +0)(0+1)*1*... And many more... Possible language are also accepted...

[@shweta7362]

@@10_yogeshchandrapandey90 thanks for clarifying :-)

[@adarshagrawal6855]

complement of a cfl may not be a cfl...cfl is not closed under complement...

[@subhadipde4873]

But complement of RL is RL, so complement of L(A) is RL. So, complement of L(A) is also context free

[@nSackStyles]

How in the world is (0+1)* = (0+1)* 0* 1* ???? Makes no sense.

[@derouvilleguillaume5416]

Given that (0+1)* can be described as: a succession of "0 or 1" an infinite amount of time or epsilon (empty, so none), you could get any variation of 0s followed by 1s (and inverse), and both regular expression would satisfy it: why ? Because you could always consider 0* 1* as empty strings, same inside (0+1)* e.g. Lets take an example string: "0000100001": - It is satisfied by this regular expression "(0+1)* 0* 1*", if "00001" comes from "(0+1)*" , 0000 comes from "0*" and 1 from "1*" - It is also satisfied by "(0+1)*", as it represents any succession of 0 or 1, or none Now, lets take 10000: - It is satisfied by this regular expression "(0+1)* 0* 1*", if "1" comes from "(0+1)*" , 0000 comes from "0*" and empty string / epsilon from "1*" - It is also satisfied by "(0+1)*", as it represents any succession of 0 or 1, or none

[@yohanesmesay8250]

option number 4 is not correctly interpreted

[@prashantupadhyay177]

Option A is correct ( 1 and 3 only)

[@sMKUMARSAISKLM]

no

[@sayantaniguha8519]

Why on minimizing the DFA we still get 3 states ?

[@birajpaul4060]

No, it will have 2 states

[@ElifArslan-l9g]

thank you

[@shusenacademy]

What does L(A) mean ?

[@nachiketagrawal5154]

Language accepted by machine A

[@TejBR0]

opamp video are not there in anolog electronics....please upload the video as soon as ..POSSIBLE

[@rajudebnath6353]

Sir plz make a video on merger table and merger graph...Also on information lossless machine..

[@shivamshah6854]

Please sir upload more video related to gate

[@akSingh_120]

great!!!

[@alessandromorelli5866]

4 is false, 3 is false, so answer is C

[@ayeshatahir1556]

cs401 assignment no.1 ka solution upload kr dyn

[@phanindrareddy4885]

Please tell me when u will complete the theory of computation

[@ricaspinto]

sir you are craizy

[@continnum_radhe-radhe]

❤❤❤

[@shanu90ful]

Very nice sir 😃

[@subhasyadav6048]

sir please upload video on FPGA and GAL

[@agamgill9563]

Nyc explation....

[@frontend.made.eazzzy]

L(G)=(11*0+0)(0+1)* it should be the language..

[@rohithpalakurthi3697]

Same doubt

[@Shivam-eh5fc]

No,buvnesh (0+1)* is a universal set so if we multiply 0*1* then also the language covers all sets of strings

[@jugheadtn5900]

You save my Life

[@phanindrareddy4885]

Sir please complete toc by may month

[@ayeshatahir1556]

sir kindly cs401 assignment no.1 2019

[@neelesh621]

howz statement 2 correct...??

[@akarshkumar2171]

C=(11*0+0)(0+1)* . As u see the dfa given, (0+1)* denotes the self loop of c for input 0 and 1. So even if u add 0*1*, the string will be at final state C. So 2nd statement is correct

[@vinayaksharma-ys3ip]

💯👍💯💯

[@annawickramasinghe2983]

[@orzAR26]

The option for this question is so DUMB!

[@_facepunch_]

Point 4 says: " A accepts all strings of length > 1 " What you think the point 4 says : " A only accepts strings of length > 1 " This means that point 4 is correct..... So..... Either whole question is wrong or 1 of point 1 or point 2 is wrong WTF...... GATE sucks

[@sunitadaga6400]

Facepunch Gaming No. It is clearly written "At least". The question is correct!

[@_facepunch_]

Sunita Daga does this FA accept any string of length 2? Yes Does this FA accept any string of length 3 ? Yes Length 4 ? Yes Length 5? Yes Does this FA accepts all string of length atleast 2? Yes.... This means that point no. 4 is True

[@JohnB-cp9se]

it is correct, point 4 is false because it can accept length 1 aswell on input 0. so its not only atleast 2.

[@_facepunch_]

John B in point 4 it is not written that this fa ONLY accept strings of length > 2....... 'ONLY' changes the meaning of the point 4

[@grimreaper-ce6kr]

It cannot accept 11 (length 2)..it says A accepts all strings of length>=2....hence false

[@zerobit778]

Does he forget add parenthesis in 10:40? Thanks~