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:

Music:
Axol x Alex Skrindo - You [NCS Release]

#TOCByNeso

[hostelboy]

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

[RA-gvys]

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

[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.

[snim]

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

[akarshkumar]

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.

[Shivam-ehfc]

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.

[N]

Have my Semester Exam Tomorrow and luckily I found this today

[nachiketagrawal]

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

[saimyousuf]

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

[_yogeshchandrapandey]

@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...

[yashmane]

if first 2 options we get as right option, then why we check that will came automatically false

[satyakumar-vczj]

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

[leninsingh]

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

[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.

[HishaMized]

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

[sukritimacker]

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

[udbhavvikramsingh]

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

[nSackStyles]

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

[siddharth.chandani]

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

[bdjeosjfjdskskkdjdnfbdj]

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