Construction of Mealy Machine (Example 1)
HTML-код
- Опубликовано: 13 окт 2024
- TOC: Construction of Mealy Machine - Examples (Part 1)
This lecture shows how to construct a Mealy Machine for a language that accepts all strings over {a,b} that ends with either 'aa' or 'bb'.
Contribute: www.nesoacademy...
Website ► www.nesoacademy...
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Pinterest ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
• Axol x Alex Skrindo - ...
The entire playlist is very useful... thank you!
this is wrong example, it will give output 010 for string aab or bba. 1 is appearing even if the string does not ends with aa or bb.
This example is correct for the question "if the string contains aa or bb" not ends with.
Edit :
turns out, i was wrong, it is correct. The string 010 is ending with zero so it will not accept. It should give output ending with 1 to get accepted.
He didn't clarify that the input is only "accepted" if the output *ends* with 1. Very ambiguous.
@@ChristianBurnsShafer means?
Sochne vali bat to h bhaiya🤔🤔
you are saying output is 010 , what is wrong then ? ==> Accept the string when right most digit is 1. it's that simple , if right most digit is 0 . This indicates that the string you have entered is not accepted.
You're right. There shouldn't be self-loops for a/1 and b/1, but 2 different states, hence, the correct machine will have 5 states and not 3. I made the correct one before looking at his solution and got confused, thank you so much for your comment !
I read the comments and saw people not getting the question the question is to have a machine that accepts strings taht have aa/bb at the end , is a string like aaba can't be accepted , but a string like aa, bb, aabb, abaa ,etc are accepted , and that's all the machine does so if you getting out put as 010 ,well your string of inputs is wrong(not accepted) why because 1 only represent , the completion of a sequence aa/bb in the string , so yes you can get a string like aab and you will have out put like 010 but that shows you the string is not ending with bb or aa and also tells that ther is one pair is aa or bb in the strong
Neso u Must clarify this example if u respect your subscribers! This example seems wrong.. like others have mentioned in the comment section.. is it ok(safe?) to assume that whenever we encounter aa or bb in a string we have output 1? instead of accepting strings that end with aa or bb its more like pointing out how many ''aa' ' or/and ''bb'' an input string has *( if we add the '1' s in the ouput sequence)
I think i'm right guys this is the correct question (video 38) Conversion of Mealy Machine to Moore Machine (Example 1) ruclips.net/video/rkgbhngdJ5Y/видео.html
Yes this is wrong
So what the problem i mean yes you can count how many aa or bb ate in the string if you can multiple of them ,but the question is not how may aa/bb are there the question is , it (machine ) must accept any string ending with aa/bb it could be aabaa aaabb , aa ,bb
never stop neso....lots of love
East or west Neso Academy is the best.
Sir,
How do you determined that it will give output 1 for aa and bb.I am getting confused.
Can you explain it.
I have another solution starting state A on getting input a gives output(0) and goes to state B, A on getting input b gives output(0) and goes to state D, B on getting input a gives output(1) and goes to state C, B on getting input b goes to state D and gives ouput(0), D on getting input b goes to state E and gives output(1), D on getting input a goes to state B and produce output(0).
Correct me if i am wrong.
this is not DFA, in state C and E there is no outgoing transitions.
There must be a condition for producing such mealy machine, and that is :-
Condition -- Machine only accept those strings for which, MSB in output string is 1, else it is considered as not accepting the input strings.
If the output must also meet the criteria of the 1 being at the end. Doesn't it mean that we should create another FSM like DSA to determine whether the output is correct? Meaning that we need two FSM's in total?
That is what i was thinking. Mealy machine generates the string corresponding to the input string and then we use another FSM to check whether the output string is accepted or not. If it gets accepted then the original string ends with aa or bb.
Very useful..thanks a lot
Wrong solution, as it will produce 1 when ever the sequence aa or bb appears in input. while the question says output 1 only when aa or bb appears in end only.
Sir Mealy machine will only generate the output string consisting of 0 and 1. We need to create another machine to check the acceptance of the o/p string. If the output string gets accepted then the original input string ends with aa or bb and if not then the input string does not end with aa or bb.
It seems that either the question is something different or your machine is wrong. Please check it and explain if I am wrong.
I am really late but still, our aim here is just to create a mealy machine that will accept a string if it ends with aa or bb.the strings can be aaabb, baa,aaaabb etc
In the previous video titled 'Construction of Mealy machine', the question was to print 'a' whenever sequence 01 is encountered or print 'b' otherwise. So in that video when 0 occurred the flow went from state A to state B with output b and when again 1 occurred in the input i.e. when we got the desired sequence the flow went from state B to state C with the output 'a'.But in this video when aa was detected the flow remained on state B itself outputting a 1 (similarly for state C when bb is detected) instead of going to another state like it was done in the previous video. Please explain.
Note that string 'aaa' has the string 'aa' occuring in it twice. Once for the first two a's and once for the last two a's. If we move away after counting the first, then we won't count the second. In particular input 'aaa' returns output '011' which we accept.
@@ChristianBurnsShafer this would count the number of occurrences of aa and bb but in the question it is asking for ending with aa and bb
@@AyushEditz-hs6pf Oh shit good call. There would be the first aa, second aa, and aaa, e.g.
nice lecture
this example is wrong it will print 1 whenever it encounters with aa or bb. not when a string ends with aa or bb. make a dfa which accepts strings ending with aa and bb and then assign 1.
thanks a lot sir for clearing the doubt.
you are doing a very nice work.
Neso Academy Nice.
+Neso Academy Your use of the term "accepted" is what's causing the problems here. You should simply state "the output will end in 1 if the input ends in aa or bb" if that's what you mean.
Dfa has a final state, melay and moore doesnt… fundamental flaw in your concept
Nice Sir 😊
what about input aab aur bba string?
it print 1 but not ended with aa or bb.
aa takes to state B with output =1 ; Now if in that state you apply another input b then you move to state C. the output =0 because the sequence is a-->a output =1 when you enter b it transitions from a-->b output =0. Guess it helps
He didn't clarify that the input is only "accepted" if the output *ends* with 1. Very ambiguous.
A Mealy machine does not have final states because it does not accept or reject input. Instead each transition produces output.
The output string has to end with 1 only.
bba mat akr no scope
Design a mealy machine that scans sequence of input of 0 and 1 and generates output 'A' if
the input string terminates in 00, output 'B' if the string terminates in 11, and output 'C'
otherwise. Solve this One problem
Thank You💙
the solution you gave
it accept the string which contain aa or bb in anywhere of the string
please give right answer
Thankyou sooo much sir...for explanation 👍👍
i love NESO
only less than 3 ??
i love NESO >3....i love NESO greater tham 3
What about aaabbb, the output will be 011011, i think it needs clarification should it count all aa or just paired aa
If I give input as aaa it prints 011 so here aaa is accepted
You should mention the final state
sir how u take the output aa =1 and bb=1? getting confused sir!
for string abba also it is showing 1 , but that's not correct , as it should end with aa or bb
if we give input as aab or bba it still gives 1 which means something is wrong.
Great video , but the example is incorrect - aaa will produce 1,1 which is wrong as 1,1 should be produced when aaaa is inputed
Insted of taking 2 stages and placing a self loop in 2nd stage why don’t we take 3 stage’s A->B->C
It is a bit confusing.the question should be "the string contain aa or bb" not end with aa or bb.
It's correct question, the thing is we have to focus only on the last output bit obtained
is final state not necessary in mealy machine ? as in this example no final stae is there though strings ends with either aa or bb
so, if the input is aaa, will the output be 011 ? is that right ?
yes but it seems confusing, don't know if that was the expected behaviour or not
Could you please an example of drawing a waveform timing diagram from a state diagram of a mealy machine
Why are there no final state(s) in the machine?
Tysm sir....
Sorry Sir , but the DFA is incorrect.. This DFA counts the number of occurrences of either a or b...
Sorry Sir , but this is Mealy Machine.. not DFA...
How to design a mealy machine that increment binary number by 1?
String from sigma* means??
If we give input as abbaa, we get output as 00101, is it okay?
👍👍
String must end with aa / bb . If you get the 1 at the last the string will be acceptable otherwise not. Appearance of 1 in middle doesn't matter at all.
check for string 'aaa' it will produce output '011' . Isn't it wrong?
String 'aaa' ends in 'aa' and output '011' ends in 1, which is the intended way for this machine to work.
where did the final state go in these examples?
There is no initial and final state in mealy machine
@@nilshrestha9147 why is that?
Because it doesn't reject the input like in DFA, it means that it gives some output for every input...
No .mealy meachine has initial stage but not has final stage.
A day before exam in 2x speed
what about AAABBB?
Yes, it would accept...we are concerned about the last output of the machine(it would accept only if the last output is 1)...since the ending state is BB, so the last output is 1 and thus it accepts...
29
What if they string is babbb ?
00011
A bit confusing but ok
ok