I kinda understood the notation after he explained it but I have no idea *why* we're using this notation - it has so little connection with the conventional meanings of the symbols used, and is so insufficient to describe the functionality of the machine. the use of Greek symbols instead of natural English names, and the use of an extremely ambiguous/overloaded math syntax instead of something more like a programming language with a very simple and regular syntactic structure is infuriating
14:48 EE -> TT -> FF -> aa. You could interpret a* as exponentiation but I think that in general this leads to ambiguity if you're interpreting the CFG as a model for arithmetic.
49:35 I don't think this example language actually does require nondeterminism? If you just pop everything that matches the current input and push everything that doesn't, and accept if the stack is empty at the end, it should still work. For example, the stack for the sample input (011110) would go 0 -> 01 -> 0 -> 01 -> 0 -> empty. I would try and write out the mathematical notation but I don't have the best grasp on that yet...
This approach is wrong. If we take your model and give input 1100, at the end of the string, the stack will be empty but given string is not part of the language still it is accepted. And nondeterminism is required to check at which symbol w has been ended and reverse of the w has been started.
40:50 Here, I thought when epsilon is on the right side of the transition function, it means we popped the top from the stack, not that it was unchanged and that we didn’t write. I thought unchanged is when it’s the same symbol as the one on the left
I think the definition of (deterministic) PA is every transition needs to either push or pop stack, to add epsilon to stake is to remove such constraint to support nondeterministic PA. I guess the epsilon of stack on the left hand size means you don't need to pop (read) to transition state, and the epsilon on the right hand side means you don't need to push (write) to transition. If you read the examples in the textbook it will be more clear.
I think one flaw with PDA while checking whether a string is in a CFL or not is that CFL can be infinite. So essentially the checking process might not ever terminate.
You have to distinguish two types of meaning, one way is infinite as you describe, another is given any number said n we can show result is true. In here we show the proof in the sense of the second meaning.
@1:08:20 Here a student states that NFA and DFA are equivalent. Prof Siper states that this is not true. In the last lecture ( ruclips.net/video/KAySmSEGc9U/видео.html ) he states this IS true. And in fact we showed that we can model a NFA by using the powerset on the states of a DFA. Even empty strings can be substituted. I was wondering if I got this wrong or whether he just wanted to state that the "general" functionality of a DFA and NFA are different in principal.
NFA and DFA _are_ equivalent. However, an NFA with a stack (a non-deterministic pushdown automaton) is not equivalent to a DFA with a stack (a deterministic pushdown automaton). Does this help?
It looks like he kept the R rule separate because it has a different variable. Since CFGs are tied to their variables (as defined in CFG - Formal Definition @ 8:20). So although your compact version produces the same language, but it's a different CFG - since it doesn't have an R rules.
Funny how the writer of the book I have on my left is also giving me a lecture at the same time.
Haha, same!
Studying for midterm by binging these videos, these are amazing
Legend Sipser!
calm down muhammed
Very helpful. Thanks for the input, sir. Much appreciated.
@22:30 there is a 3rd meaning: the boy saw (as cut in half with a saw) the girl...
I thought that too, but it would be improper grammar. The proper way to say it would be “The boy sawed the girl with the mirror.”
the ambiguity that he was referring to is on the structure of the sentence and not on the meaning of the words
42:20 prof sipser a real one
I kinda understood the notation after he explained it but I have no idea *why* we're using this notation - it has so little connection with the conventional meanings of the symbols used, and is so insufficient to describe the functionality of the machine. the use of Greek symbols instead of natural English names, and the use of an extremely ambiguous/overloaded math syntax instead of something more like a programming language with a very simple and regular syntactic structure is infuriating
@@gloverelaxis skill issue
14:48 EE -> TT -> FF -> aa. You could interpret a* as exponentiation but I think that in general this leads to ambiguity if you're interpreting the CFG as a model for arithmetic.
49:35 I don't think this example language actually does require nondeterminism? If you just pop everything that matches the current input and push everything that doesn't, and accept if the stack is empty at the end, it should still work. For example, the stack for the sample input (011110) would go 0 -> 01 -> 0 -> 01 -> 0 -> empty. I would try and write out the mathematical notation but I don't have the best grasp on that yet...
This approach is wrong. If we take your model and give input 1100, at the end of the string, the stack will be empty but given string is not part of the language still it is accepted. And nondeterminism is required to check at which symbol w has been ended and reverse of the w has been started.
@@jaiminvaghela4576 ahhhh makes sense!
Anthropomorphizing the machine
40:50 Here, I thought when epsilon is on the right side of the transition function, it means we popped the top from the stack, not that it was unchanged and that we didn’t write. I thought unchanged is when it’s the same symbol as the one on the left
I think the definition of (deterministic) PA is every transition needs to either push or pop stack, to add epsilon to stake is to remove such constraint to support nondeterministic PA. I guess the epsilon of stack on the left hand size means you don't need to pop (read) to transition state, and the epsilon on the right hand side means you don't need to push (write) to transition. If you read the examples in the textbook it will be more clear.
The boy saw the girl with the mirror.
meaning number 3: you can read it as he cut her in half with a mirror. : )
57:15 Sipser's a funny guy
28:28 Pushdown automata.
I think one flaw with PDA while checking whether a string is in a CFL or not is that CFL can be infinite. So essentially the checking process might not ever terminate.
You have to distinguish two types of meaning, one way is infinite as you describe, another is given any number said n we can show result is true. In here we show the proof in the sense of the second meaning.
Very helpful to future students! Great work! Thank you!
23:43 a + a + a actually doesn't belong to G2. Then how are L(G2) = L(G3)
a + a + a is in G2, try to use the first rule to generate 3 terms and reduce from there.
Till 27:24
"The boy saw the girl with the mirror" could specify the location of the girl with respect to a particular mirror.
or could mean saw as in cutting with a saw lol
@1:08:20 Here a student states that NFA and DFA are equivalent. Prof Siper states that this is not true. In the last lecture ( ruclips.net/video/KAySmSEGc9U/видео.html ) he states this IS true. And in fact we showed that we can model a NFA by using the powerset on the states of a DFA. Even empty strings can be substituted. I was wondering if I got this wrong or whether he just wanted to state that the "general" functionality of a DFA and NFA are different in principal.
NFA and DFA _are_ equivalent. However, an NFA with a stack (a non-deterministic pushdown automaton) is not equivalent to a DFA with a stack (a deterministic pushdown automaton). Does this help?
4:10 Can G₁ be simplified to S → 0S1 | ε?
It looks like he kept the R rule separate because it has a different variable. Since CFGs are tied to their variables (as defined in CFG - Formal Definition @ 8:20).
So although your compact version produces the same language, but it's a different CFG - since it doesn't have an R rules.
@@ndeoligence8 That makes a lot of sense, thank you!
Yes!
Yes, That's a simplified CFG without a NULL production rule.
21:36
Another meaning can be that the boy saw(🪚) the girl using the mirror.
But it's not grammatically correct. Should be 'saws'
I'm shocked... I just realized that the book included in my course by Michael sipser & I'm getting lecture py same professor....🫢🫢🫢❤❤❤