Regular Languages
Vložit
- čas přidán 20. 12. 2016
- TOC: Regular Languages in Theory of Computation.
Topics Discussed:
1. Regular Languages in TOC.
2. Non-Regular Languages in TOC.
3. Examples of languages which are not regular.
Full Course on TOC: goo.gl/f4CmJw
Follow Neso Academy on Instagram: @nesoacademy (bit.ly/2XP63OE)
Follow me on Instagram: @jaiz_itech (bit.ly/2M3xyOa)
Contribute: www.nesoacademy.org/donate
Memberships: bit.ly/2U7YSPI
Books: www.nesoacademy.org/recommende...
Website ► www.nesoacademy.org/
Forum ► forum.nesoacademy.org/
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
#TheoryOfComputation #TOCByNeso #RegularLanguages #AutomataTheory
Why is the first example not a regular language? If the language just consists of one string then can't you just have all the states of the machine be Q ={a, ab, abb...} and then the transition function for each state would be whether the next symbol is seen, and if it isn't, we send the machine to a dead state?
EDIT: I just saw your reply to a different comment. I didn't understand the example. For those wondering the example was about whether it can detect if a string repeated itself.
Wonderful video! Everything is explained in such a clear and efficient way. You're the best.
I freaken love you and this channel for this content!
Amazing content.Keep up the good work.
This was such a good video. Very clear. Thank you
Thank you sir for your clear explanation, this series really saves me!!! God bless you!
the first example can be modelled in a FSM. First u make a tree structured DFM with 'a' for left and 'b' for right. then wherever u end up at the fifth character, u continue accordingly.
Exactly!
U could also make an NFA ith an epsilon transition back to the start after reading ababb
Yeah I also found that :( It really confused me
i think this is true only if the alphabet is equal to {a,b}. if the alphabet includes more symbols your solution would be wrong
yes
i like your lectures , brother. you got one more subscriber.
i love they way you explain things.
wow what a nice video you made very clear and very easy...
To be clear.
Let S to be a string. We could have DFA to recognize S* just simply by loop to the beginning after a full match. What Neso mean is just that we could not have a DFA to find a arbitrary S's repetition. To recognize a specific string's repetition is a different story with arbitrary string's repetition!!!
if ababb needs to be repeated exactly n times then we increase the number of states (copy the FM n times) wouldn't that work?
((A))-a->((B))-b->((C))-a->((D))-b->((E))-b->(((F))) - - a - -> ((B)) - -
NFA for any non-integer repetition.
(A)-a->(B)-b->(C)-a->(D)-b->(E)-b->(F)- - a - ->(B2)-b->(C2)-a->(D2)-b->(E2)-b->((F2))
NFA for exactly 2 repetitions.
@@whiteheadiceprince1506 This string you mean "ababa" is a specific one. You can have DFA for this specific string for any repetition of times.
But the DFA you constructed for "ababa" may not work for other string like "abcabc".
What Neso mean is you can not have DFA works for all types of string with repetitions.
@@zerobit778 ohh ok thank you
very helpful
The first Eg. (ababbababb) repeats only 2 times, so without saving it we can simply construct a DFA that gets all inputs as a sequence of alphabets. In this case isn't it regular language?
Pail guy and Calvin, you're both correct
If the repeating part of the string is of finite length, I think we can construct DFA for it.
I think what he meant to say is that, we can't construct a DFA that accepts all strings that are arbitrary repetition of a smaller string.
But can't we construct a DFA for any number of ababb substring to occur?
For the first example (ababb)* is a regular expression that generates the string of the first example. Since there is a regular expression, there is also a finite machine. Instead, my language accepts even when ababb is repeated n times (n greater or equal to 0). Maybe, the guy on video implies what Tapaj says.
The rule for language 1 is: 'The first n Symbols repeat once'. These n symbols can be anything. Just as an example he mentioned ababb.
Totally helpful
Awesome video...
The expression ( ababbababb ) that you discussed earlier in this lecture is regular expression and you say: it's not a regular
thank you sir
Thanks
You said that a language is regular if it can be recognized by FSM. RegEx has a lot of modifiers that allow it to count repetition or use memory. Eg. "{2}" is a quantifier - Match 2 of the preceding token. Or "\1" is Backreference - matches the result of capture group #1. Does that make Regular Expressions not a regular language? I'm a little confused...
Yes.
Thank You
can you explain that why ababbababb is not recognizing with FSM ? i can create ababbababb by using 10 state(one state point to dead conditions) simply.
Yes, although you can make it, the question here is, suppose you want user to just input "ababb" and insert rest of the values yourself to generate the result, such action would be possible if we have some sort of memory from which we could retrieve the values and use them as input to run our machine further on its own without user intervention, however in FSM, user must give some input to move states, there is no dedicated memory bank that could provide input to machine.
Thankyou sir
I'm missing the explaination why finite state automata cannot count or store strings. Maybe an example where we try to build a fsm that tries process these langages but fails would have been useful.
It doesn't store any previous input of the string that has been provided. You only move forward with the current input. For eg. if w is a string with symbol {a, b} so to recognize ww, you need to store w first, which is not possible in FSM.
Don't get how FSM can't store strings when in the previous lectures of DSM we transfer all string to next state(or that's how I understood it )
The degree of complexity and the way of performing the functions
characteristic. Automatic Grade 1
Respected Sir
In the second example, can we not make a DFA with an infinite number (limited only by total memory available) of states in a line, each moving forward on input A and back on input B? That way we can keep our initial and final state the same and still have a way to count the number of A's and b's.
it shouldn't be of the form ababab, but should be aaaa....bbbb....
@@eeshaan1539 Agreed, but what trying to imply is making a ladder.... Ababab strings would never reach the initial/final (because they're the same) state without having an equal number of A's and b's... Imagine going up 3 steps and coming down 3 steps as an analogy
Now that I think about it.... This is quite impractical. A DFA needs full information about all states and I can't define how the start and end states would be structured
By the way is a language over {a,b} that contains aabb in itself regular or not
Please make a video of the proof of the first theorem you wrote !! I have an exam in two days , I know it is too late for me but for other generations maybe not so late :)
Lol too late... Have exam tomarrow
@@nameless2850 every cs video's fate I guess...
Good luck ,man !!
@@deadoralivecowboy1401 and now my fate🥲
@@abhisheknegi2888 Now mine
My time has come… I have exam in 3 days 😅
Theoretically you could build a state Machine which recognizes the second language, as long as you can build a machine with 2*n-states
Thank you..
What r various models to represent regular language
Respected sir
By using 6 states + 1 dead state we can construct a dfa for ababbababb
Your dfa only accepts ababbababb but it should accept any ww where w is a string thats why we cant use dfa
I doubt if 6 suffices, we need 10 + 1 dead state.
costruct regular grammer for language is avalible or not......?
amazing
Awesome
Thank you Sir for explaining this ,is regular language same as regular expression?
No
If you can design RE, you can derive RL and vice versa
A video of what is regular language that shows examples only of non-regular languages. Don't you think it would be a good idea to illustrate that regular language is?
THANKS..
What if you define the language in the first example as follows:
L = {V, S, T, P}
where,
V = {a, b, S, A}
T = {a, b}
P = {S->Ab, A->AbAb, A->abab}
Would that not make the example a regular language, unlike the second one in which a memory of N is required?
yeah I also don't think his first example is valid
The first language is regular as it can be represented L={(ababb)^n : n>=1), provided lambda is not accepted, for which a DFA can be constructed.
why is second one not a regular language in when in previous video we designed a dfa fo aabb which follows the structure aNbN n=2?
I think it's because in this video, it's not only n=2, but for all natural numbers (i.e.: n≥1).
Actually ababbababb is a regular language
If the language is just that you can have a simple machine which recognizes the string.
If the language is "ababb" repeated n times you can still have a machine which recognizes it: just 5 states to recognize the basic string, only the last state is a final state and if you are in the final state and read an "a" you start over from the first state
I also think so, we can easily construct nfa for that
It is not asking if you can check if the string "ababb" is repeating.
It is asking us to check if we need to memorize an arbitrary string. Our Finite Acceptors can only remember a singular state so it would require an infinite amount of nodes to remember every possible arbitrary string.
how do we know how to split the "aaaaaaabbbbbb" into x y z ? is it just random
more formal way to define a regular language would be that it can be described by a regular expression.
And what if its a language that start with a and finish with b ?
Is this language {(0^n)(1^m)|(n+m)is even} regular or not?
Is not regular because you need to count n and m to know that the sum is even.
@@raulcalvomartin2979 No, it is regular! Checking whether n+m is even does not require you to remember n and m completely, it is enough to remember the remainder modulo 2, which can be done with finitely many states.
you forgot to put an example of a regular language... almost a perfect video
all the 4 examples before are regular languages, yall lazy.
example 1 is a string, not language,which we can represent using DFA
It's for recognizing M1M2, where M1 is a string and M1=M2, that's the rule for the language.
if Σ=(0,1) then describe Σ* 1Σ*
Answer pls?
watching all the videos one day before the exam on 2x
#Excelent!
List some examples of regular language's
I don't understand practically about regular expression i just understand the theory.
Regular Language -> if some FSM recogonizes it.
FSM -> Very low memory.
my teacher plays your videos in lectures
finally found a good video, jesus...
Praise the Lord
Good but spoiled a bit by specifying five letters specifically and not N letters. With five (or some other constant) letters the language is finite and you can construct a DFA for it, it is regular. If it is some arbitrary number of letters than you cannot.
didn't get much idea
Is this lecture value for gate and other competitive exams?
this lecture is very fruitful for concept on regular language. a good concept can only make one solve questions
fix the audio, please
Can u provide ur class notes
set the speed to 2x
It's good that he goes slow, allowing you to speed the video up when you need to, and leave it as it is when necessary as well.
Why?????????
is there a proof for repetition --> non regular? seems like a bit of a leap for me!
haha
Pumping lemma is the proof
speed of 1.5 is sufficient for beginners
8 like Shaun Tait!
But provided that language is finite,it will be regular....please mention it
I didn't understand the first example. ababbababb. I think we can design a DFA for it.
The language is { ww : w is a string over Sigma} i.e. the first and second halves of the string must be same. ababbababb is one of the strings in this language, but it's not the only one.
lol I have final exam next week let's see if ness will make me pass
now i have final exam next week so can you tell that are you pass or fail? :D :P
what happened?
I hav xam nxt morning and found this video only now time :12:45am
video bht achi h but urdu me hoti to or be achi hoti
👍👍👍
sorry sir, but first example is incorrect ...if L is regular and L^2 is also regular ...refrence introduction to FLA edition 5th by peter linz Fig 2.7 page 46
I think he meant to find strings that are in the form of XX (that X could be any string), which is impossible to be found by a finite state machine.
kaisa machine hai jo ek count ko bhi store nahi kar sakta hai
yeah, right. Just like you dumbass XD
lol
1.75x,, you are welcome
Any KECian😂
「どうやってやるの？」、
Any vitian😅
Thanks alot sir
Thanks