Video
Đăng bởi Cô Lan (Giáo viên) ·
[SQUEAKING] [RUSTLING] [CLICKING] MICHAEL SIPSER: So, welcome, everybody,
[TIẾNG KÊU] [TIẾNG XÀO XÀO] [NHẤP CHUỘT] MICHAEL SIPSER: Vậy thì, Chào mừng mọi người!
to the Fall 2020 online Introduction to the Theory of Computing 18.404/6.840.
đến kỳ học trực tuyến mùa Thu năm 2020 Giới thiệu về lý thuyết Khoa Tin học 18.404/6.840.
My name is Mike Sipser. I'm going to be your instructor for the semester in this class. So let me just tell you what the course is about.
Tôi tên là Mike Sipser. Tôi sẽ là người hướng dẫn của bạn. cho học kỳ này ở lớp học này. Vậy để tôi nói cho bạn biết nhé. Khóa học này nói về điều gì.
Basically, it's going to be in two halves. We're going to be talking about what are the capabilities and limitations of computers — of computer algorithms, really, computation.
Về cơ bản, nó sẽ... Chia làm hai nửa. Chúng ta sẽ nói chuyện. về những khả năng và những hạn chế của máy tính — các thuật toán máy tính, Thực ra, đó là tính toán.
And the two parts of the course are more or less divided in half.
Và hai phần của các khóa học được chia thành nhiều phần khác nhau. chia đôi.
The first half of the course is going to talk about a subject called computability theory, which it really asks what you can compute with an algorithm in principle.
Nửa đầu của Khóa học đang diễn ra để nói về một chủ đề có tên là lý thuyết tính toán, mà Câu hỏi thực sự là gì? bạn có thể tính toán Về nguyên tắc, đó là một thuật toán.
That's — was an active area of research in the earlier part of the 20th century.
Đó là một khu vực hoạt động tích cực của nghiên cứu ở phần đầu của thế kỷ 20.
It's pretty much closed off as a research subject these days, mainly because they answered all of their big questions.
Nó gần như đã đóng cửa hoàn toàn. được chọn làm đối tượng nghiên cứu ngày nay, chủ yếu là vì họ đã trả lời tất cả những câu hỏi lớn của họ.
And so a mathematical field really only stays vital when it has problems to solve, and they really solved all of their interesting problems — for the most part, not 100%.
Và do đó, một phương trình toán học lĩnh vực thực sự chỉ vẫn giữ được sức sống khi nó có những vấn đề cần giải quyết, và họ thực sự đã giải quyết được tất cả các vấn đề. những vấn đề thú vị của họ — Phần lớn là vậy, nhưng không phải 100%.
But for the most part, it sort of finished off in the 1950s — just to say a little bit more about what we're going to talk about there.
Nhưng nhìn chung thì nó khá là... đã hoàn thành vào những năm 1950 — chỉ để nói một chút thôi Tìm hiểu thêm về chúng tôi Tôi sẽ nói về điều đó ở đó.
When you're interested to know what kinds of problems you can solve with an algorithm — there are problems that you might want to solve that you just can't solve.
Khi bạn quan tâm đến biết những loại vấn đề nào bạn có thể giải quyết bằng một thuật toán — có vấn đề mà bạn có thể muốn giải quyết vấn đề đó Bạn không thể giải quyết được.
For example, given a specification for a computer problem you want to solve, whatever that specification might be — say your algorithm actually is a sorting algorithm, for example — and you want to write down that specification and have an automatic verifier that's going to check whether a program meets the specification.
Ví dụ, cho một thông số kỹ thuật của máy tính vấn đề bạn muốn để giải quyết, bất kể Thông số kỹ thuật đó có thể là — hãy nói về thuật toán của bạn thực chất là một sự phân loại ví dụ như thuật toán — và bạn muốn viết theo thông số kỹ thuật đó và có một cái tự động người xác minh đó là sẽ kiểm tra xem liệu Chương trình đáp ứng các yêu cầu kỹ thuật.
Well, that's just in principle impossible. You cannot make a verifier which is going to answer, in all cases, whether or not a program meets a certain specification.
Vâng, đó chỉ là... Nguyên tắc này là bất khả thi. Bạn không thể tạo trình xác minh Điều này sẽ trả lời, trong mọi trường hợp, bất kể một chương trình đáp ứng một số tiêu chí nhất định Thông số kỹ thuật.
So with things like that, we will prove this semester. Questions about mathematical truth — if you're given a mathematical statement, is it true or is it false?
Vì vậy, với những vấn đề như vậy, Chúng ta sẽ chứng minh điều đó trong học kỳ này. Câu hỏi về chân lý toán học — nếu bạn được giao một bài toán Lời tuyên bố đó có đúng không? Hay điều đó là sai?
It'd be great if you can write a computer program that would answer that problem. Well, it would not be great if you were a mathematician, because that would put us all out of business.
Sẽ thật tuyệt nếu bạn có thể Viết một chương trình máy tính để sẽ giải quyết được vấn đề đó. Chà, điều đó sẽ không tốt lắm. Nếu bạn là một nhà toán học, bởi vì điều đó sẽ đặt Chúng ta đều mất hết công việc kinh doanh rồi.
But you can imagine that might be a nice thing to have, but you can't. I mean, there is no algorithm which can answer that question.
Nhưng bạn có thể hình dung ra điều đó Có lẽ đó là một điều tốt nên có. Nhưng bạn không thể. Ý tôi là, không có thuật toán nào cả. Điều đó có thể trả lời câu hỏi đó.
Well, along the way, we're going to introduce models of computation, like finite automata, which we'll see today, Turing machines, and some other models that we'll see along the way.
Vâng, trên đường đi, chúng ta sẽ giới thiệu các mô hình của tính toán, giống như hữu hạn máy tự động, mà chúng ta sẽ Hãy xem ngày nay, máy Turing, và một số mô hình khác Chúng ta sẽ cùng xem xét điều đó trên đường đi.
The second half of the course, which is going to be after the midterm, we're going to shift gears and talk about complexity theory, which is instead of looking at what's computable in principle, you're going to look at what's computable in practice, so things that you can solve in a reasonable amount of time.
Nửa sau của khóa học, mà sẽ là sau kỳ thi giữa kỳ, chúng ta sẽ chuyển số và nói chuyện về lý thuyết độ phức tạp, mà thay vì nhìn vào những gì đang diễn ra có thể tính toán được trong nguyên tắc, bạn sẽ đi để xem xét những gì có thể tính toán được trên thực tế, nên mọi thứ mà bạn có thể giải quyết trong một khoảng thời gian hợp lý.
And, for example, I'm sure many of you are aware of the factoring problem, which has connections to the RSA cryptosystem, cryptography, and asks whether you can factor big numbers quickly.
Ví dụ, Tôi chắc chắn rằng nhiều người trong số các bạn nhận thức được việc phân tích thành nhân tử vấn đề, có liên hệ đối với hệ thống mã hóa RSA, mật mã học, và hỏi liệu bạn có thể tính đến yếu tố đó hay không. Số lượng lớn một cách nhanh chóng.
That's a problem we don't know the answer to. We just don't know how to factor big numbers quickly.
Đó là một vấn đề của chúng ta Tôi không biết câu trả lời. Chúng tôi chỉ không biết phải làm thế nào Phân tích các số lớn một cách nhanh chóng.
But it's possible that there are algorithms out there that we haven't discovered yet that can do so.
Nhưng có thể là có Liệu có thuật toán nào tồn tại ngoài kia không? mà chúng ta chưa khám phá ra nhưng điều đó hoàn toàn có thể.
It's connected with this very famous problem in the intersection of computer science and mathematics called the P versus NP problem, which many of you may have heard of.
Nó có liên quan đến vấn đề rất nổi tiếng này tại ngã tư khoa học máy tính và toán học được gọi là Bài toán P so với NP, cái nào Nhiều người trong số các bạn có thể đã nghe nói đến.
We'll talk about that. We'll spend a lot of time on that this term.
Chúng ta sẽ bàn về chuyện đó sau. Chúng ta sẽ dành nhiều thời gian thời gian dành cho việc đó trong học kỳ này.
And along the way, we'll talk about different measures of complexity, of computation, time and space, time and memory, theoretical memory, electrical space.
Và trên đường đi, chúng ta sẽ thảo luận về các biện pháp khác nhau về độ phức tạp, của tính toán, thời gian và không gian, thời gian và trí nhớ, lý thuyết Bộ nhớ, không gian điện.
That's going to be a big part of the course in the complexity theory part — introduce other models of computation, such as probabilistic and interactive computation. Talk about the expectations of the course.
Đó sẽ là một phần quan trọng. của khóa học về độ phức tạp phần lý thuyết — giới thiệu những người khác mô hình tính toán, chẳng hạn như xác suất và Tính toán tương tác. Hãy nói về Những kỳ vọng về khóa học.
First of all, prerequisites. There are a bunch of prerequisites listed, 6.042, 18.062 , or maybe some other subject as well. The real thing is that this is a math class.
Trước hết, cần đáp ứng các điều kiện tiên quyết. Có rất nhiều các điều kiện tiên quyết được liệt kê, 6.042, 18.062, hoặc có thể là một số nào đó cũng như các môn học khác. Sự thật là Đây là lớp học toán.
This is a class where — and it's not a beginning math class, this is a moderate-to-advanced math class.
Đây là một lớp học mà — và nó không phải là một lớp toán cơ bản, Đây là trình độ từ trung bình đến nâng cao. lớp toán.
And I'm expecting people to have had some prior experience, of a substantial nature, with mathematical theorems and proofs. We'll start off slow, but we're going to ramp up pretty fast.
Và tôi đang mong đợi mọi người đã từng có có kinh nghiệm trước đó, có tính chất quan trọng, với toán học các định lý và chứng minh. Chúng ta sẽ bắt đầu chậm rãi, nhưng chúng ta sẽ... Sẽ tăng tốc khá nhanh.
So if you haven't really got the idea or gotten comfortable with doing proofs, coming up with proofs to mathematical statements, that's going to be a concern.
Vậy nên nếu bạn chưa thực sự đã hiểu ý tưởng hoặc đã cảm thấy thoải mái với đang làm chứng minh, sắp tới kèm theo bằng chứng các phát biểu toán học, Đó sẽ là một vấn đề đáng lo ngại.
I would just be monitoring yourself and seeing how you're doing.
Tôi chỉ đơn giản là tự giám sát bản thân và xem bạn thế nào rồi.
Because the homeworks and the exams are going to count on your being able to produce proofs, and so you're going to be struggling if that's going to be a real — something that you haven't had experience with.
Vì bài tập về nhà và các kỳ thi sẽ trông cậy vào khả năng sản xuất của bạn bằng chứng, và vì vậy bạn sẽ gặp khó khăn Nếu đó thực sự là... một điều gì đó mà bạn chưa từng có đã có kinh nghiệm với.
And let me talk a little bit about the role of theory in computer science. This is a theory class, as you know.
Và cho phép tôi nói một chút. một vài điều về vai trò về lý thuyết trong khoa học máy tính. Đây là một giả thuyết. như bạn đã biết, lớp học.
So before we jump into the material, I just thought it would be worth it for you to give you at least my perspective on the role of theoretical computer science within the field.
Vậy trước khi chúng ta bắt đầu vào vật liệu, Tôi chỉ nghĩ rằng nó sẽ Sẽ xứng đáng với bạn để cung cấp cho bạn tại ít nhất là theo quan điểm của tôi về vai trò của lý thuyết khoa học máy tính trong lĩnh vực này.
So I've been in computer science for a long time.
Tôi đã làm việc trong lĩnh vực máy tính. Khoa học từ lâu rồi.
I go back — I'm sure I'm getting to be a dinosaur here — but I go back to the days when you had punch cards. That's what we did when I was an undergraduate.
Tôi quay lại — Tôi chắc chắn là tôi Sắp trở thành khủng long ở đây rồi! nhưng tôi nhớ về những ngày xưa thời mà người ta còn dùng thẻ đục lỗ. Đó là những gì chúng tôi đã làm khi Tôi là sinh viên đại học.
And, obviously, things are very different now. And you can argue that computer science as a discipline has matured, and sort of the basic stuff has all been solved.
Và, rõ ràng là, mọi thứ Bây giờ thì khác lắm rồi. Và bạn có thể tranh luận khoa học máy tính đó khi một ngành học đã trưởng thành, và những thứ cơ bản Mọi vấn đề đã được giải quyết.
Well, I would say there's a certain truth to that, but there's a certain way in which I would say that's not true.
Tôi nghĩ là có Điều đó có phần đúng. nhưng có một một cách nào đó Tôi cho rằng điều đó không đúng.
I think we're still at the very beginning, at least in certain respects, of computer science as a discipline.
Tôi nghĩ chúng ta vẫn còn Ngay từ đầu, ít nhất là trong một số trường hợp nhất định về mặt khoa học máy tính như một ngành học.
For one thing, there are a lot of things that we do, a lot of things relating to computation, that we just don't know the answer to — very fundamental things.
Thứ nhất, có Có rất nhiều thứ Chúng tôi làm rất nhiều việc. liên quan đến tính toán, chúng ta không hề biết câu trả lời cho — rất Những điều cơ bản.
Let's take as an example, how does the brain work? Obviously, the brain computes in a certain fashion.
Chúng ta hãy lấy ví dụ, Não bộ hoạt động như thế nào? Rõ ràng, bộ não thực hiện tính toán. theo một cách nào đó.
And we've made good progress, you can argue, with machine learning and all of those things that have very — very powerful and doing very cool things.
Và chúng ta đã làm tốt tiến bộ, bạn có thể lập luận như vậy. với máy học và tất cả trong số những thứ có rất — rất mạnh mẽ và Đang làm những việc rất tuyệt vời.
But I would also say that at some deeper level, the methods that we have so far don't allow us to understand creativity.
Nhưng tôi cũng muốn nói rằng tại ở một mức độ sâu sắc hơn, các phương pháp những điều mà chúng ta cho đến nay vẫn chưa cho phép Giúp chúng ta hiểu về sự sáng tạo.
We're not close to being able to create a computer program that can do mathematics or that can do many of the creative kinds of things that human beings can do.
Chúng ta còn lâu mới có thể tạo ra một chương trình máy tính mà có thể làm toán hoặc có thể làm được nhiều người sáng tạo các loại đồ vật Những điều mà con người có thể làm được.
I think machine learning, powerful as it is, is really successful only for a very narrow set of tasks.
Tôi nghĩ về học máy, dù mạnh mẽ đến đâu, thực sự thành công chỉ vì Một tập hợp nhiệm vụ rất hạn chế.
And so I think there's probably something deeper and more fundamental going on that we're missing. That would be my hunch.
Vì vậy, tôi nghĩ có lẽ là có một điều gì đó sâu sắc và hơn thế nữa những điều cơ bản đang diễn ra những gì chúng ta đang bỏ lỡ. Đó là linh cảm của tôi.
Now, whether something like theoretical computer science is going to give you an answer there — or this kind of theory, or some kind of theory — I think some kind of theory has at least a decent shot at playing a role in helping us to understand computation in a deeper way.
Giờ thì, liệu có phải là một điều gì đó như khoa học máy tính lý thuyết là Tôi sẽ trả lời bạn. ở đó - hoặc loại lý thuyết này, hoặc một loại lý thuyết nào đó — Tôi nghĩ đó là một loại lý thuyết nào đó. ít nhất cũng có cơ hội khá tốt đóng vai trò giúp đỡ giúp chúng ta hiểu về tính toán theo một cách sâu sắc hơn.
And the fact that we can't understand something as basic as, can you factor a big number quickly or not? You can't really say you understand computation until you can answer questions like that.
Và thực tế là chúng ta không thể hiểu một điều gì đó là cơ bản vì vậy, bạn có thể tính toán một yếu tố lớn Tính số nhanh hay chậm? Bạn không thể thực sự nói rằng bạn hiểu về tính toán cho đến khi bạn có thể trả lời Những câu hỏi kiểu như vậy.
So I would argue that we have a really very primitive understanding of computation at this stage and that there is a lot that has yet to be discovered, not just on the technological side, but just on the very fundamental theoretical side that has a real shot at playing a role in affecting the practice of how we use computers.
Vì vậy, tôi cho rằng chúng tôi có một thứ thực sự rất sự hiểu biết sơ khai về quá trình tính toán ở giai đoạn này và có rất nhiều điều đó vẫn chưa được khám phá. không chỉ trên khía cạnh công nghệ, nhưng chỉ ở khía cạnh cơ bản nhất. khía cạnh lý thuyết đó có cơ hội thực sự để chơi một vai trò trong việc ảnh hưởng thực hành như thế nào Chúng ta sử dụng máy tính.
And so I think for that reason — again, I'm not sure what kind of theory is going to be the most useful, but the theory we're going to cover in this course is a particularly elegant theory, and it has already paid off in many applications and in terms of our understanding of computation.
Và vì vậy tôi nghĩ rằng... vì lý do đó — một lần nữa, Tôi không chắc đó là loại lý thuyết nào. Đây sẽ là điều hữu ích nhất. nhưng lý thuyết mà chúng ta đang theo đuổi là... những nội dung sẽ được đề cập trong khóa học này là một đặc biệt lý thuyết thanh lịch, và nó đã thanh toán rồi. tắt trong nhiều ứng dụng và về mặt của chúng ta Hiểu biết về tính toán.
And I think, at least as a starting point, it's a good subject to learn. Certainly, I enjoy it, and I've spent a good chunk of my career doing that.
Và tôi nghĩ, ít nhất là như một điểm khởi đầu, Đây là một môn học hay. Chắc chắn rồi, tôi rất thích nó, và Tôi đã dành một khoản tiền khá lớn. Tôi đã dành cả sự nghiệp của mình để làm việc đó.
So let's move on then and begin with the subject material.
Vậy chúng ta hãy tiếp tục và bắt đầu thôi. với nội dung môn học.
So we're going to talk about models of computation, as I mentioned. We want to try to understand computers, and we want to understand what computers can do.
Vậy chúng ta sẽ nói chuyện. về các mô hình tính toán, như tôi đã đề cập. Chúng tôi muốn thử hiểu biết về máy tính, và chúng tôi muốn hiểu Những gì máy tính có thể làm được.
But computers in the real world are pretty complicated objects, and they're really not nice to talk about mathematically.
Nhưng máy tính trong thế giới thực Chúng là những vật thể khá phức tạp. và họ thực sự không tốt bụng chút nào. Để nói về mặt toán học.
So we're going to talk about abstract models of computers that are much simpler but really capture — just like models in general — capture the important aspects of the thing we're trying to understand.
Vậy chúng ta sẽ nói về mô hình trừu tượng của máy tính đơn giản hơn nhiều nhưng thực sự nắm bắt được — Giống như các người mẫu nói chung — nắm bắt những điều quan trọng các khía cạnh của sự vật Chúng tôi đang cố gắng hiểu.
And so we're going to look at several different kinds of models that vary in their capabilities and the way they approximate the real computers that we deal with every day.
Vì vậy, chúng ta sẽ xem xét ở nhiều loại khác nhau các mô hình khác nhau về khả năng và cách thức chúng xấp xỉ những chiếc máy tính thực sự Những điều chúng ta gặp phải hàng ngày.
And for starters, we're going to look at a very simple model called the finite automaton.
Và trước tiên, chúng ta sẽ đi để xem xét một mô hình rất đơn giản được gọi là máy tự động hữu hạn.
And that's going to represent — you can think of it as representing a computer that has a very small amount of memory and a very limited and small amount of memory.
Và điều đó sẽ thể hiện — bạn có thể coi nó như đại diện cho một máy tính mà có kích thước rất nhỏ lượng bộ nhớ và rất hạn chế và Dung lượng bộ nhớ nhỏ.
And we're going to look at the capabilities of those kinds of machines. And what's nice about them is that you can understand them very well.
Và chúng ta sẽ xem xét ở khả năng thuộc loại máy móc đó. Điều tuyệt vời ở chúng là để bạn có thể hiểu họ Rất tốt.
And so more powerful models that we're going to look at later are going to be harder to understand in as deep a way.
Và do đó, các mô hình mạnh mẽ hơn Chúng ta sẽ xem xét điều đó sau. sẽ khó khăn hơn Hiểu một cách sâu sắc nhất.
But for these, we can develop a very comprehensive theory. And so that's what we're going to do for the next lecture and a half. So I'm starting off with an example.
Nhưng đối với những trường hợp này, chúng ta có thể phát triển. Một lý thuyết rất toàn diện. Và đó là những gì chúng ta sẽ làm. những việc cần làm cho bài giảng tiếp theo và một nửa. Vậy là tôi bắt đầu Ví dụ.
I'm presenting a finite automaton as a diagram — we call it a state diagram.
Tôi đang trình bày một giới hạn hữu hạn Sơ đồ người máy tự động — Chúng ta gọi đó là sơ đồ trạng thái.
It has these circles and lines and labels on the lines and also on these circles. So what's going on here? So this is a finite automaton.
Nó có những vòng tròn này và các đường kẻ và nhãn trên các đường kẻ và cả trên những vòng tròn này nữa. Vậy chuyện gì đang xảy ra ở đây? Vậy đây là một máy tự động hữu hạn.
I'm giving it the name M1. And it has — these circles are called states. So in this case, there were three states, q1, q2, and q3.
Tôi đặt tên cho nó là M1. Và nó có— những điều này Các vòng tròn được gọi là các tiểu bang. Vậy trong trường hợp này, có... ba trạng thái, q1, q2 và q3.
Those are the labels there. There are arrows connecting states with each other. So these we'll call transitions. And they're going to tell you how to compute with this device.
Đó là các nhãn dán. Có các mũi tên nối liền nhau. các tiểu bang với nhau. Vậy chúng ta sẽ gọi đây là các giai đoạn chuyển tiếp. Và họ đang đi để cho bạn biết cách để thực hiện tính toán với thiết bị này.
And there's going to be a specially-designated starting state, which has an arrow coming in from nowhere.
Và sẽ có một khởi đầu được chỉ định đặc biệt trạng thái, có một mũi tên Xuất hiện từ hư không.
And there are other specially-designated states called accepting states, and that's going to have to do with how the machine computes. But those are the ones that have these double circles.
Và còn có những thứ khác nữa. các tiểu bang được chỉ định đặc biệt được gọi là chấp nhận các tiểu bang, và đó là sẽ liên quan đến Cách máy tính hoạt động. Nhưng đó là những người mà Chúng có những vòng tròn kép này.
And so talking about the way it computes, the idea is pretty simple. The input is going to be some finite string of 0's and 1's, in this case.
Và vì vậy, khi nói về cách thức tính toán của nó, Ý tưởng này khá đơn giản. Đầu vào sẽ là là một chuỗi hữu hạn nào đó Trong trường hợp này, đó là các số 0 và 1.
We might have other types of symbols that are allowed for other automata, but the example that I have here, it's going to be 0's and 1's.
Chúng ta có thể có các loại khác. các ký hiệu được phép đối với các automata khác, nhưng Ví dụ mà tôi có ở đây, Nó sẽ toàn là số 0 và số 1.
And the way you compute with the thing is you first put your finger — which I can't do on Zoom, so I'll use the pointer — you put your pointer on the starting state, the one that has the arrow coming in from nowhere.
Và cách bạn tính toán với thứ đó là khi bạn đặt ngón tay đầu tiên — Điều mà tôi không thể làm trên Zoom. Vậy nên tôi sẽ dùng con trỏ — bạn đặt con trỏ của bạn ở trạng thái ban đầu, cái có mũi tên Xuất hiện từ hư không.
First, you put your pointer there. And then are you start reading symbols from the input, one after the next. So let's take an example here, 01101.
Đầu tiên, bạn đặt Con trỏ của bạn ở đó. Và sau đó bạn là ai bắt đầu đọc các ký hiệu từ đầu vào, Hết cái này đến cái khác. Vậy chúng ta hãy lấy một Ví dụ ở đây, 01101.
So you start reading those symbols, and you follow those transitions. So you go 0 — and you go back to the same state.
Vậy là bạn bắt đầu đọc những biểu tượng đó, và bạn theo dõi những sự chuyển đổi đó. Vậy là bạn đi 0 — và bạn quay trở lại đến cùng một tiểu bang.
Then you go — the next symbol is a 1, so you go over to this state, from q1 to q2. Now you have another one that comes in.
Rồi bạn đi — cái Ký hiệu tiếp theo là số 1. Vậy nên bạn hãy đi sang đây. trạng thái, từ q1 đến q2. Giờ bạn lại có thêm một cái nữa. một người đến.
So now you're starting at q2, you have another one, so you follow its associated transition. So if you notice, every state has an outgoing transition for 1 and another outgoing transition for 0.
Vậy bây giờ bạn bắt đầu từ Câu hỏi 2, bạn còn một câu hỏi nữa. Vì vậy bạn hãy làm theo hướng dẫn của nó. quá trình chuyển đổi liên quan. Vậy nên nếu bạn để ý, mỗi tiểu bang đều có một quá trình chuyển đổi đi ra cho 1 và một sự chuyển đổi đi khác với 0.
So there's always somewhere to go every time you read symbols from the input. So now you're at q2. You read that next, that third symbol, which is a 1.
Vì vậy, luôn có một nơi nào đó để đi mỗi khi bạn đọc các biểu tượng từ đầu vào. Vậy là bây giờ bạn đang ở quý 2. Bạn sẽ đọc tiếp phần đó, Ký hiệu thứ ba, đó là số 1.
That's going to take you over to q3. And now you have a 0, which loops you back to where you were, and another 1, which loops you back to where you were.
Điều đó sẽ Đưa bạn sang câu hỏi 3. Và giờ bạn đã có 0, điều này sẽ đưa bạn vào vòng lặp. trở lại nơi bạn đã từng, và một số 1 khác, số này sẽ lặp lại bạn Trở lại nơi bạn đã từng.
And because you ended up at an accept, you say we accept that string.
Và bởi vì bạn đã kết thúc chấp nhận ở mức độ nào đó, Bạn nói chúng ta chấp nhận chuỗi ký tự đó.
So that's going to be the output of this finite automaton. For each string, it's either going to accept it or reject it. So it's just a binary decision that is going to be made.
Vậy đó sẽ là Kết quả đầu ra của máy tự động hữu hạn này. Đối với mỗi chuỗi ký tự, Hoặc là nó sẽ đi Chấp nhận hay từ chối điều đó. Vậy nên đó chỉ là một quyết định nhị phân. Điều đó sẽ được thực hiện.
It's sort of like a 1 or a 0 output, but we're calling it accept or reject. So this one here, because it ended up at the accepting state, is accepted.
Nó đại loại như... Đầu ra là 1 hoặc 0, nhưng chúng tôi đang gọi Nó chấp nhận hoặc từ chối. Vậy thì cái này đây, vì cuối cùng nó đã khi chấp nhận Trạng thái này được chấp nhận.
But if you look at the second example, 00101, so you're going to have 0, 0, 1, 0, 1. Now we ended up at q2.
Nhưng nếu bạn nhìn vào Ví dụ thứ hai, 00101, vậy nên bạn sẽ có 0, 0, 1, 0, 1. Giờ thì chúng ta đã đến quý 2 rồi.
That's not an accepting state. So therefore, we say we reject this input. OK? Very simple.
Đó không phải là một trạng thái chấp nhận. Vì vậy, chúng ta nói rằng Chúng tôi từ chối dữ liệu đầu vào này. ĐƯỢC RỒI? Rất đơn giản.
And now, for example, one of the questions you might want to ask, given one of these things, is, well, which are exactly those strings that the machine accepts?
Và bây giờ, ví dụ, một trong những câu hỏi Bạn có thể muốn hỏi, Nếu có một trong những điều này, là, ừm, những cái nào chính xác những chuỗi đó Máy đó chấp nhận cái gì?
And a little bit of thought will help you understand that the only strings which are going to take you over to q3 are those strings that have a 11 appearing somewhere along the way, two consecutive 1's, and you will end up at the accepting state.
Và một chút suy nghĩ sẽ giúp ích bạn hiểu điều đó những chuỗi duy nhất chúng sẽ chiếm lấy bạn đến câu hỏi 3 là những chuỗi đó có số 11 xuất hiện Trên đường đi, có hai người các số 1 liên tiếp, và bạn sẽ cuối cùng đạt đến trạng thái chấp nhận.
I encourage you to think about that for a minute if not immediately obvious. But those are the strings that are going to be accepted by this machine.
Tôi khuyến khích bạn suy nghĩ Về chuyện đó một chút nếu không dễ nhận thấy ngay lập tức. Nhưng đó là những sợi dây đang đi Để được máy này chấp nhận.
And we call that collection of strings the language of the machine.
Và chúng ta gọi đó là tập hợp các chuỗi Ngôn ngữ của máy móc.
So that set A of those strings that have a 11, for this particular machine, is the language of M1. We also say that M1 recognizes that language, recognizes A.
Vậy tập hợp A của những chuỗi đó có số 11, cho trường hợp cụ thể này. Máy móc là ngôn ngữ của M1. Chúng tôi cũng nói rằng M1 nhận biết Ngôn ngữ đó nhận ra A.
And in terms of notation, we write that A is L of M1. A is the language of M1. So the language of a machine is exactly the set of strings that machine accepts.
Và về mặt ký hiệu, chúng ta viết rằng A là L của M1. A là ngôn ngữ của M1. Vậy ngôn ngữ của máy móc là gì? chính xác là tập hợp các chuỗi Máy đó chấp nhận.
OK? So one of the first things we're going to want to be able to do is take a machine and understand what its language is, what's the set of strings that that machine accepts.
ĐƯỢC RỒI? Vậy nên một trong những việc đầu tiên chúng ta cần làm là... sẽ muốn có thể làm được lấy một cái máy và hiểu điều gì Ngôn ngữ của nó là gì? tập hợp các chuỗi mà máy đó chấp nhận.
Another thing we might want to do is, given a language, build a machine which recognizes that language. And then understanding, what are the class of languages?
Một điều khác mà chúng ta có thể muốn Việc cần làm là, khi đã cho một ngôn ngữ, chế tạo một cỗ máy mà nhận biết ngôn ngữ đó. Và sau đó hiểu được điều gì Chúng thuộc loại ngôn ngữ nào?
Can you get any language from some machine, or are there going to be some languages that you can do and other languages that you cannot do?
Bạn có thể sử dụng bất kỳ ngôn ngữ nào không? từ một loại máy nào đó, hoặc liệu sẽ có một số những ngôn ngữ bạn có thể học và các ngôn ngữ khác Điều đó bạn không thể làm được sao?
So those are the kinds of questions we're going to be asking about these finite automata. What kinds of things can those machines do, and what can they not do?
Vậy đó là các loại câu hỏi chúng ta sẽ hỏi Về các automata hữu hạn này. Những loại đồ vật nào Những cỗ máy đó có thể làm được gì? Vậy họ không thể làm được gì?
OK. Here's our next check-in.
ĐƯỢC RỒI. Đây là lần cập nhật tiếp theo của chúng tôi.
So wake up, everybody who's not paying attention. A check-in is coming. So we have more questions, though I can't keep — are these three statements equivalent?
Vậy nên, mọi người hãy tỉnh dậy đi! người không chú ý. Sắp đến giờ nhận phòng. Vậy là chúng ta có nhiều hơn những câu hỏi, mặc dù tôi không thể giữ lại — đây có phải là Ba câu phát biểu tương đương nhau?
What three statements?
Ba câu phát biểu đó là gì?
AUDIENCE
At the bottom of the slide.
Tại đáy của cầu trượt.
MICHAEL SIPSER
Oh, oh, oh, oh, oh, yes. Those three are equivalent. A is the language — yeah, those mean the same thing.
Ồ, Ồ, ồ, ồ, ồ, đúng vậy. Ba cái đó tương đương nhau. A là ngôn ngữ — đúng vậy, Chúng có nghĩa giống nhau.
Not only are they equivalent, but they're just different ways of saying the same thing.
Chúng không chỉ tương đương nhau, nhưng chúng chỉ là những cách khác nhau thôi cũng có nghĩa tương tự.
That M1 recognizes the language is the same as saying that's the language of the machine and that A equals that L of M. That's all the same way of saying they all — six of one, half a dozen of the other.
Điều đó có nghĩa là M1 nhận ra ngôn ngữ là Tương tự như việc nói rằng đó là ngôn ngữ của máy móc và rằng A bằng Đó là chữ L của M. Đó là tất cả đều có cùng một cách nói như vậy. tất cả— sáu cái một, nửa tá của người kia.
It's two ways of saying the same thing. OK, so let's pop up our poll and get that started. Whoops.
Có hai cách Cũng nói điều tương tự. Được rồi, vậy chúng ta hãy bật lên nào. Hãy tiến hành thăm dò ý kiến và bắt đầu thực hiện việc đó. Ối.
Still showing the old one — oh, here we go. Move it to the next question. OK.
Vẫn còn hiển thị những thứ cũ một- ồ, bắt đầu rồi. Hãy chuyển nó sang câu hỏi tiếp theo. ĐƯỢC RỒI.
OK, so you understand the question here? Where do we end up after we read 101? What state are we in?
Được rồi, vậy là bạn hiểu rồi. Câu hỏi ở đây là gì? Cuối cùng chúng ta sẽ đi đến đâu? Sau khi chúng ta đọc xong chương 101? Chúng ta đang ở tiểu bang nào?
Do we end up in state q1, q2, or q3?
Liệu cuối cùng chúng ta có rơi vào tình huống... Trạng thái q1, q2, hay q3?
OK? Go fast.
ĐƯỢC RỒI? Đi nhanh lên.
This is a — OK, so I think we got pretty much converged here.
Đây là một — Được rồi, vậy tôi nghĩ chúng ta đã đạt được Hầu hết các ý kiến đều hội tụ tại đây.
I think almost everybody got it right. The answer is indeed that you ended up in state q2. Because you go 1, 0, 1, and that's where you ended up, in state q2.
Tôi nghĩ gần như vậy Mọi người đều trả lời đúng. Câu trả lời đúng là như vậy. Bạn đã rơi vào tình trạng q2. Vì bạn đi số 1, 0, 1, và đó là Nơi bạn kết thúc, ở trạng thái q2.
So is this string accepted? No, because you didn't end up at an accept state. So this machine rejects 101. OK, let's keep going.
Vậy chuỗi ký tự này có được chấp nhận không? Không, vì bạn không làm thế. Kết thúc ở trạng thái chấp nhận. Vậy máy này từ chối 101 sản phẩm. Được rồi, chúng ta tiếp tục nào.
So now — yeah.
Vậy bây giờ thì... ừ.
OK, so now we gave it this informal idea of a finite automaton.
Được rồi, vậy là bây giờ chúng ta đã cho ý tưởng không chính thức này của một máy tự động hữu hạn.
We're going to have to try to get a formal definition now, which is going to be a more mathematical way of saying the same thing that I just said.
Chúng ta sẽ phải cố gắng Hãy tìm định nghĩa chính thức ngay bây giờ. điều này sẽ trở nên hơn cách nói toán học Cũng giống như những gì tôi vừa nói.
And the reason for having a formal definition is, for one thing, it allows us to be very precise.
Và lý do cho việc đó là một định nghĩa chính thức Thứ nhất, nó cho phép Chúng tôi, nói một cách chính xác nhất, là như vậy.
Then we'll know exactly what we mean by a finite automaton, and it should answer any questions about what counts and what doesn't count. It also is a way of providing notation.
Khi đó chúng ta sẽ biết chính xác điều gì Chúng ta hiểu "máy tự động hữu hạn" là như sau: và nó sẽ trả lời bất kỳ những câu hỏi về điều gì được tính và những gì không được tính. Nó cũng là một cách Cung cấp ký hiệu.
So it'll help us describe finite automata.
Vì vậy, nó sẽ giúp ích cho chúng ta. Mô tả các automata hữu hạn.
And sometimes there might be an automaton where the picture is just too big, so you might want to be able to describe it in some mathematical terminology rather than by giving a picture.
Và đôi khi có thể có một người máy tự động, trong đó có hình ảnh quá lớn, nên bạn có thể muốn có thể mô tả nó trong một số toán học thuật ngữ thay vì Thay vì chỉ đưa ra một bức ảnh.
Or maybe you're going to be asked to give a family of automata, where there is going to be a parameter, N, associated with the class of languages you're trying to describe with the automaton.
Hoặc có thể bạn là sẽ được hỏi để tặng cho một gia đình của máy tự động, trong đó Sẽ có một tham số, N, liên quan với lớp các ngôn ngữ bạn đang thử Để mô tả bằng máy tự động.
And then it'll be more helpful to describe it in this formal notation rather than as a kind of a picture, because it might be infinitely many pictures that are being needed.
Và sau đó nó sẽ còn hơn thế nữa. Việc mô tả điều đó sẽ rất hữu ích. trong ký hiệu chính thức này hơn là một loại tranh vẽ, bởi vì nó có thể là vô số bức ảnh đang cần thiết.
So maybe examples of that will come up now. So a finite automaton, we call it a 5-tuple. Don't be put off by that. A 5-tuple is just a list of five things.
Vậy có thể là một vài ví dụ về Điều đó sẽ được đề cập ngay bây giờ. Vậy nên, đó là một máy tự động hữu hạn. Chúng ta gọi đó là bộ 5 phần tử. Đừng để điều đó làm bạn nản lòng. Một bộ 5 phần tử chỉ đơn giản là một Danh sách năm điều.
So a finite automaton, in our definition, is going to have five components.
Vậy nên, đó là một máy tự động hữu hạn. theo định nghĩa của chúng tôi, sẽ có năm thành phần.
It's going to have Q, which is going to be a finite set of states, so it's going to be a finite set, which we'll designate as the states of the automaton.
Nó sẽ có Q, đang đi là một tập hợp hữu hạn của các tiểu bang, vì vậy nó là sẽ là một tập hợp hữu hạn. mà chúng ta sẽ chỉ định như các trạng thái của máy tự động.
Sigma is the alphabet symbols of the automaton, another finite set.
Sigma là chữ cái trong bảng chữ cái. các biểu tượng của người máy tự động, một tập hợp hữu hạn khác.
Delta is the transition function. That tells us how the automaton moves from state to state.
Delta là Hàm chuyển đổi. Điều đó cho chúng ta biết cách thức hoạt động của người máy tự động. Di chuyển từ tiểu bang này sang tiểu bang khác.
Those describes how those transition arrows — those arrows which connected the states with each other — it describes them in a mathematical way instead in terms of a picture.
Những điều đó mô tả như thế nào những mũi tên chuyển tiếp đó — những mũi tên kết nối các tiểu bang với nhau — nó mô tả chúng trong một cách toán học thay vào đó là xét về mặt hình ảnh.
And the way I'm doing that is with a function. So delta is a function which takes two things. So I'm hoping you've seen this notation before.
Và theo cách tôi đang làm Đó là với một hàm. Vậy delta là một hàm số Điều này đòi hỏi hai yếu tố. Vậy nên tôi hy vọng bạn đã xem rồi. ký hiệu này trước đó.
I'll help you through it once, but this is the kind of thing I would expect you to have seen already. So we have Q cross sigma.
Tôi sẽ giúp bạn vượt qua Trước đây thì không, nhưng lần này thì không là loại điều tôi mong đợi Bạn chắc hẳn đã thấy rồi. Vậy ta có Q chéo sigma.
So I'm going to give delta a state and an alphabet symbol. So Q is states, sigma is alphabet symbols.
Vậy nên tôi sẽ cho delta một trạng thái và một ký hiệu chữ cái. Vậy Q là các trạng thái, sigma là các ký hiệu bảng chữ cái.
So you're going to get a state and an alphabet symbol, and it's going to give you back a state.
Vậy nên bạn sẽ nhận được một trạng thái và một ký hiệu chữ cái, và nó sẽ Trả lại cho bạn một tiểu bang.
So describing it kind of a little bit more detail, delta, if you give it state q and symbol a equals r, that means q, when you read an a, you go to r.
Vì vậy, việc mô tả nó đại khái là như thế này. Thêm một chút chi tiết nữa, delta, nếu bạn cung cấp trạng thái cho nó q và ký hiệu a bằng r, điều đó có nghĩa là q, khi bạn Đọc chữ a, bạn chuyển sang chữ r.
So that's the way this picture gets translated into a mathematical function, which describes those transitions. And then now q0 is going to be the starting state.
Vậy nên đây là cách thức hoạt động của nó. hình ảnh được dịch thành một toán học chức năng, mà Mô tả những sự chuyển đổi đó. Và bây giờ q0 đang đi là trạng thái ban đầu.
That's the one with the arrow coming in from nowhere. And F is the set of accepting states.
Đó là cái có Mũi tên xuất hiện từ hư không. Và F là tập hợp của các tiểu bang chấp nhận.
So there's only going to be one starting state, but there might be several different — or possibly even 0 — accepting states. That's all legal when we have a finite automaton.
Vậy nên sẽ chỉ có là một trạng thái khởi đầu, nhưng có thể có một số khác nhau — hoặc thậm chí có thể là 0 — các tiểu bang chấp nhận. Tất cả đều hợp pháp khi chúng ta có một máy tự động hữu hạn.
And so in terms of using the notation — going back to the machine that we just had from the previous slide, which I've given you here again — let me show you how I would describe this using this notation that comes out of the definition.
Vì vậy, xét về mặt sử dụng ký hiệu — quay lại với cái máy đó chúng ta vừa có được từ trước đó slide, mà tôi đã Tôi lại đưa cho bạn ở đây — Để tôi chỉ cho bạn cách làm Tôi sẽ mô tả sử dụng ký hiệu này để Nó xuất phát từ định nghĩa.
So here is M1 again. It's this 5-tuple where Q now is the set — q1, q2, q3 — that's the set of states. The input alphabet is 0, 1.
Vậy là M1 lại xuất hiện. Đây là bộ 5 phần tử, trong đó Q Bây giờ là bộ — q1, q2, q3 — Đó là tập hợp các tiểu bang. Bảng chữ cái đầu vào là 0, 1.
It might vary in other automata. And f is the set q3, which has only the element q3, because this has just one accept state, q3. So I hope that's helpful.
Điều này có thể khác nhau ở các loại máy tự động khác. Và f là tập hợp q3, chỉ có yếu tố câu hỏi 3, bởi vì điều này vừa mới một trạng thái chấp nhận, q3. Tôi hy vọng điều đó sẽ hữu ích.
Oh, of course, I forgot the transition function, which here I'm describing as a table.
Ồ, tất nhiên rồi, tôi quên mất rồi. hàm chuyển đổi, mà Ở đây tôi đang mô tả nó như một cái bảng.
So the transition function says if you have a state and an input alphabet, you can look up in the table where you're supposed to go under the transition function according to the state and the alphabet symbol
Vì vậy, quá trình chuyển đổi hàm cho biết nếu bạn có một tiểu bang và một bảng chữ cái đầu vào, bạn có thể tra cứu trong cái bàn nơi bạn đang ngồi đáng lẽ phải đi xuống hàm chuyển đổi theo tiểu bang và ký hiệu bảng chữ cái
that you're given.
những gì bạn được trao.
So, for example, if we were in state q2 here getting a 0, then q2 goes back to q1 so that q2 on 0 is q1.
Ví dụ, nếu chúng ta Ở trạng thái q2, kết quả là 0. sau đó q2 quay lại q1 vậy nên q2 trên 0 là q1.
But q2 on 1 here is q3. OK? So that's how that table captures this picture. OK?
Nhưng câu hỏi 2 trên câu 1 ở đây là câu hỏi 3. ĐƯỢC RỒI? Vậy đó là cách cái bàn đó được thiết kế. Chụp bức ảnh này. ĐƯỢC RỒI?
And it's just a function. It's a way of representing a function, a finite function, in terms of this table here.
Và nó chỉ là một hàm số. Đó là một cách để biểu thị một hàm, một hàm hữu hạn, xét theo bảng này.
So I realize, for some of you, this may be slow.
Vì vậy, tôi nhận ra, đối với một số người Đối với một số bạn, quá trình này có thể diễn ra chậm.
We will ramp up in speed, but I'm trying to get us all together in terms of the language of the course here at the beginning.
Chúng tôi sẽ tăng cường về tốc độ, nhưng tôi cố gắng bắt tất cả chúng ta cùng nhau về mặt của ngôn ngữ của khóa học này bắt đầu ngay từ đầu.
OK, so now let's talk about some more the computation, so strings and languages.
Được rồi, giờ chúng ta hãy... Hãy nói thêm về một số điều khác nữa. phép tính, vậy nên Chuỗi ký tự và ngôn ngữ.
A string is just a finite sequence of symbols from the alphabet.
Chuỗi chỉ là một chuỗi hữu hạn các ký hiệu từ bảng chữ cái.
This class is not going to talk about infinite strings. All of our strings are going to be finite.
Lớp học này sẽ không Hãy nói về những chuỗi vô hạn. Tất cả các loại dây của chúng tôi đều là Sẽ có giới hạn.
There's other mathematical theories of automata and so on that talk about infinite inputs and infinite strings. We're not going to talk about that.
Còn có những vấn đề toán học khác nữa. lý thuyết về máy tự động và cứ thế tiếp tục cuộc nói chuyện đó về đầu vào vô hạn và những chuỗi vô tận. Chúng ta sẽ không Hãy nói về điều đó.
Maybe rarely, we'll make it very clear, we'll talk about an infinite string, but that's going to be an exception. And a language is a set of strings.
Có lẽ hiếm khi, chúng ta sẽ Hãy nói thật rõ ràng, chúng ta sẽ nói về một chuỗi vô hạn, nhưng chuyện đó sẽ xảy ra là một ngoại lệ. Và ngôn ngữ là một tập hợp các chuỗi.
That's the traditional way that people in this subject refer to a set of strings. They call it a language — really because the subject had its roots in linguistics, actually.
Đó là cách truyền thống. những người trong chủ đề này Tham chiếu đến một tập hợp các chuỗi ký tự. Họ gọi đó là ngôn ngữ — thực sự là vì chủ đề có nguồn gốc từ Thực ra là ngôn ngữ học.
And they were talking about — they're trying to understand languages, human languages. So this is just a historical fact, and that's the terminology that's stuck.
Và họ đang nói chuyện về — họ cố gắng hiểu Ngôn ngữ, ngôn ngữ của con người. Vậy đây chỉ là một Sự thật lịch sử, và đó là Thuật ngữ đã trở nên phổ biến.
OK, so two special string — a special string and a special language. The empty string is the string of length 0.
Được rồi, vậy là có hai sợi dây đặc biệt — một sợi dây đặc biệt và một ngôn ngữ đặc biệt. Chuỗi rỗng là Chuỗi có độ dài 0.
This is a totally legitimate string that you are going to run into now and then. And there's the empty language, which is the set with no strings. These are not the same.
Đây là hoàn toàn chuỗi hợp lệ bạn sẽ thỉnh thoảng gặp phải. Và còn có ngôn ngữ trống rỗng, điều đó Đây là bộ không có dây buộc. Chúng không giống nhau.
They're not even of the same type of object. So don't confuse them with one another. I mean, you can have a set, a language, which has just one element, which is the empty string.
Họ thậm chí không phải là... cùng loại đối tượng. Vì vậy đừng nhầm lẫn chúng với nhau. với nhau. Ý tôi là, bạn có thể có một tập hợp, một ngôn ngữ, chỉ có một thành phần, đó là chuỗi rỗng.
That is not the empty set. That is a set — that is not the empty language. That is a language that has one element in it, namely, the empty string.
Đó không phải là tập hợp rỗng. Đó là một tập hợp- đó là Không phải là những lời nói sáo rỗng. Đó là một ngôn ngữ mà Nó có một thành phần, Cụ thể hơn, đó là chuỗi rỗng.
So those are separate things.
Vậy nên đó là hai việc hoàn toàn khác nhau.
OK, so here's a little bit of a mouthful here on the slide, defining what it means for an automaton to accept its input — accepts its input string w.
Được rồi, vậy đây là một chút về Có quá nhiều thông tin ở đây trên slide. định nghĩa ý nghĩa của nó đối với một máy tự động chấp nhận đầu vào của nó — chấp nhận chuỗi đầu vào w.
And we can define that formally. And it's a little technical looking, it's really not that bad.
Và chúng ta có thể định nghĩa điều đó một cách chính thức. Và nó hơi nhỏ có vẻ ngoài kỹ thuật, Thực ra cũng không tệ lắm đâu.
So if you have your input string w, which you can write as a sequence of symbols in the alphabet — w1, w2, dot dot dot, wn, so like 01001.
Vậy nếu bạn có chuỗi đầu vào w, mà bạn có thể viết như sau: một chuỗi ký hiệu trong bảng chữ cái — w1, w2, chấm chấm chấm, wn, vậy nên giống như 01001.
I'm just writing it out symbol by symbol here. So what does it mean for the machine to accept that input?
Tôi chỉ đang viết nó ra thôi. Từng ký hiệu một ở đây. Vậy điều đó có ý nghĩa gì đối với Máy móc có thể chấp nhận đầu vào đó không?
So that means that there's a sequence of states in the machine, sequence of states of members of Q. So a sequence from Q, these are the states of the machine that satisfy these three properties down here.
Vậy có nghĩa là có một chuỗi các trạng thái trong máy, trình tự của trạng thái của các thành viên của Q. Vì vậy một chuỗi từ Q, Đây là các tiểu bang của máy móc đáp ứng ba bất động sản này ở phía dưới đây.
First of all — and I'm thinking about the sequence that the machine goes through as it's processing the input w. So when does it accept w?
Trước hết- và tôi là suy nghĩ về trình tự mà máy móc phải trải qua trong khi nó đang xử lý đầu vào w. Vậy khi nào nó chấp nhận w?
If that sequence has the feature that it starts at the start state, each state legally follows the previous state according to the transition function.
Nếu chuỗi đó có đặc điểm rằng nó bắt đầu từ đầu tiểu bang, mỗi tiểu bang về mặt pháp lý tiếp nối trạng thái trước đó theo Hàm chuyển đổi.
So that says the i-th member of the sequence is obtained by looking at the previous one — the i minus first member of that sequence, the i minus first state in that sequence — and then looking at what happens when you take the i-th input symbol.
Vậy điều đó có nghĩa là thứ i thành viên của chuỗi được thu được bằng cách nhìn ở cái trước đó — i trừ đi thành viên đầu tiên của chuỗi đó, i trừ tiểu bang đầu tiên trong đó trình tự- và sau đó xem xét điều gì sẽ xảy ra khi Bạn lấy ký hiệu đầu vào thứ i.
So as you look at the previous state and the next input symbol, you should get the next state. That's all that this is saying. And this should happen for each one of these guys.
Vì vậy, khi bạn xem xét phần trước đó trạng thái và đầu vào tiếp theo biểu tượng, bạn nên Chuyển sang tiểu bang tiếp theo. Đó là tất cả những gì đoạn văn này muốn nói. Và điều này nên xảy ra vì Mỗi người trong số những người này.
And lastly, for this to be accepted, the very last member here, where we ended up at the end of the input — so you only care about this at the end of the input — you have to be in an accepting state.
Và cuối cùng, dành cho Điều này cần được chấp nhận, thành viên cuối cùng đây, nơi chúng tôi đã đến. ở cuối phần nhập liệu — vậy là bạn chỉ quan tâm đến điều này ở cuối phần nhập liệu — bạn phải ở trong một trạng thái chấp nhận.
So you can mathematically capture this notion of going along this path.
Vì vậy, bạn có thể tính toán học. nắm bắt ý tưởng này đi theo con đường này.
And that's what — I'm just trying to illustrate that we could describe all this very formally — I'm not saying that's the best way to think about it all the time — but that it can be done.
Và đó là điều — Tôi chỉ đang cố gắng minh họa mà chúng ta có thể mô tả Tất cả điều này đều rất trang trọng — Tôi không nói đó là Cách tốt nhất để suy nghĩ về tất cả mọi thứ thời gian — Nhưng điều đó hoàn toàn có thể thực hiện được.
And I think that's something worth appreciating. OK.
Và tôi nghĩ đó là điều gì đó Đáng để trân trọng. ĐƯỢC RỒI.
So now in terms of, again, getting back — we've said this once already, but in terms of the languages that the machine recognizes, it's the collection of strings that the machine accepts.
Vậy bây giờ, xét về khía cạnh này, một lần nữa, quay trở lại — chúng ta đã đã từng nói điều này đã vậy, nhưng xét về mặt trong số các ngôn ngữ đó Máy nhận biết, đó là tập hợp các chuỗi mà máy chấp nhận.
Every machine accepts — it might accept many strings, but it always recognizes one particular language, even if the machine accepts no strings — then it recognizes the empty language.
Mọi máy móc đều chấp nhận điều đó. có thể chấp nhận nhiều chuỗi ký tự. nhưng nó luôn nhận ra một ngôn ngữ cụ thể, ngay cả khi máy móc Không ràng buộc gì cả. sau đó nó nhận ra Ngôn ngữ trống rỗng.
So a machine always recognizes one language, but it may have many, many strings that it's accepting. And we call that language the language of the machine. And we say that M recognizes that language.
Vì vậy, một cỗ máy luôn luôn nhận biết một ngôn ngữ. nhưng nó có thể có rất nhiều các chuỗi mà nó chấp nhận. Và chúng ta gọi đó là ngôn ngữ. Ngôn ngữ của máy móc. Và chúng ta nói rằng M nhận biết ngôn ngữ đó.
These three things mean the same thing.
Ba điều này có nghĩa giống nhau.
OK? And now important definition — I try to reserve the most important things or the highlighted things to be in this light blue color, if you can see that.
ĐƯỢC RỒI? Và bây giờ là một định nghĩa quan trọng — Tôi cố gắng đặt chỗ những điều quan trọng nhất hoặc những điều được đánh dấu để có màu xanh nhạt này, Nếu bạn có thể nhìn thấy điều đó.
We say a language is a regular language if there's some finite automaton that recognizes it. OK?
Chúng ta nói ngôn ngữ là một ngôn ngữ thông thường nếu có một số hữu hạn nào đó máy tự động nhận dạng nó. ĐƯỢC RỒI?
So there are going to be some languages that have associated to them finite automata that actually solve those languages, that recognize those languages.
Vì vậy sẽ có một số các ngôn ngữ có liên quan đối với họ là các automata hữu hạn mà thực sự giải quyết được những ngôn ngữ đó, những ngôn ngữ đó được nhận biết.
But there might be other languages — and we'll see examples — where you just can't solve them. You can't recognize them with a finite automaton. Those languages will not be regular languages.
Nhưng có thể có các ngôn ngữ khác — và chúng ta sẽ xem các ví dụ — trong đó Bạn không thể giải quyết chúng được. Bạn không thể nhận ra họ. với một máy tự động hữu hạn. Những ngôn ngữ đó sẽ không là các ngôn ngữ chính quy.
The regular ones are the ones that you can do with a finite automaton. That's the traditional terminology. OK, so let's continue. Let's go on from there.
Những loại thông thường là những cái mà bạn có thể thực hiện được với một máy tự động hữu hạn. Đó là truyền thống thuật ngữ. Được rồi, vậy chúng ta tiếp tục nhé. Chúng ta hãy tiếp tục từ đó.
So let's do a couple of examples. Here, again, is that same — getting to be an old friend, that automaton M1.
Vậy chúng ta hãy cùng làm một Một vài ví dụ. Đây lại là điều tương tự — trở thành người già Bạn ơi, đó là người máy M1.
Remember, its language here is the set of strings that have the substring 11.
Hãy nhớ, đó là ngôn ngữ của nó Đây là bộ của các chuỗi có chuỗi con 11.
That is that language A. Now, what do we know about A from the previous slide? Think with me. Don't just listen.
Đó là Ngôn ngữ A. Giờ thì sao? Chúng ta có biết gì về A không? Trang chiếu trước đó? Hãy cùng suy nghĩ với tôi. Đừng chỉ nghe mà thôi.
A is a regular language now, because it's recognized by some automaton.
A là một ngôn ngữ chính quy bây giờ, bởi vì nó là Được một số người máy nhận ra.
So whenever you find an automaton for a language, a finite automaton for language, we know that that language is a regular language. So let's look at a couple of more examples.
Vì vậy, bất cứ khi nào bạn tìm một người máy tự động đối với một ngôn ngữ, một ngôn ngữ hữu hạn máy tự động cho ngôn ngữ, chúng ta biết rằng ngôn ngữ đó là một ngôn ngữ chính quy. Vậy chúng ta hãy xem xét một Thêm một vài ví dụ nữa.
So if you take the language — let's call this one B, which is the strings that have an even number of 1's in them.
Vậy nếu bạn học ngôn ngữ — Chúng ta hãy gọi cái này là B, tức là cái nào? là những chuỗi có Trong đó có số lượng số 1 chẵn.
So like the string 1101, would that be in B? No, because it has an odd number of 1's. So the string 1111 has four 1's in it.
Vậy nên, giống như chuỗi 1101, Vậy đó có phải là ở ô B không? Không, bởi vì nó có một số lẻ các số 1. Vậy chuỗi 1111 Nó có bốn số 1.
That's an even number, so that string would be in B. The 0's don't matter for this language.
Đó là một số chẵn, vậy nên Chuỗi ký tự đó sẽ nằm trong thang âm B. Các số 0 không quan trọng Đối với ngôn ngữ này.
So strings that have an even number of 1's, that's a regular language.
Vì vậy, các chuỗi có một số chẵn các số 1, Đó là một ngôn ngữ chính quy.
And the way you would know that is you would have to make a finite automaton that recognizes that language. And I would encourage you to go and make that automaton.
Và theo cách bạn sẽ biết đó chính là bạn sẽ phải làm một máy tự động hữu hạn mà nhận biết ngôn ngữ đó. Và tôi khuyến khích bạn Hãy đi và chế tạo con robot đó.
You can do it with two states. It's a very simple automaton. But if you haven't had practice with these, I encourage you to do that.
Bạn có thể làm điều đó với hai tiểu bang. Đây là một cỗ máy tự động rất đơn giản. Nhưng nếu bạn chưa từng Hãy luyện tập với những điều này, Tôi khuyến khích bạn làm điều đó.
And actually, there are lots of examples that I ask you to solve at the end of chapter 1 in the book, and you definitely should spend some time playing with it if you have not yet seen finite automata before.
Và thực tế là, ở đó có rất nhiều ví dụ mà tôi yêu cầu bạn giải quyết tại Kết thúc chương 1 trong cuốn sách, và bạn nhất định nên Hãy dành chút thời gian chơi với nó. nếu bạn chưa xem Trước đây là các automata hữu hạn.
You need to get comfortable with these and be able to make them.
Bạn cần làm quen với những điều này và có khả năng tự làm ra chúng.
So we're going to start making some of them, but we're going to be talking about it at a sort of a more abstract level in a minute.
Vậy chúng ta sẽ bắt đầu tạo ra một số trong số chúng, nhưng chúng ta sẽ đang bàn tán về điều đó ở một dạng nào đó hơn Mức độ trừu tượng trong một phút.
Basically, the reason why you can solve this problem, you can make a finite automaton which recognizes the language B, is because that finite automaton is going to keep track of the parity of the number of 1's it's seen before.
Về cơ bản, lý do là tại sao Bạn có thể giải quyết vấn đề này. Bạn có thể tạo ra một máy tự động hữu hạn. nó nhận dạng ngôn ngữ B, là vì máy tự động hữu hạn sẽ theo dõi tính chẵn lẻ của số lượng số 1 Chuyện này đã từng xảy ra rồi.
This has two states, one of them remembering that it's seen an odd number of 1's so far, the other one remembering it's seen an even number of 1's before.
Điều này có hai trạng thái, một trong số họ nhớ lại rằng nó đã nhìn thấy một điều kỳ lạ số lượng số 1 cho đến nay, cái còn lại nhớ rằng nó đã được nhìn thấy trước đó có số lượng số 1 chẵn.
And that's going to be typical for these automata, finite automata.
Và đó sẽ là điển hình cho các máy tự động này, máy tự động hữu hạn.
There's going to be several different possibilities that you may have to keep track of as you're reading the input, and there's going to be a state associated with each one of those possibilities.
Sẽ có một vài khả năng khác nhau mà bạn có thể phải theo dõi trong khi bạn đang đọc dữ liệu đầu vào, và sẽ có là một tiểu bang liên kết với mỗi một trong số những khả năng đó.
So if you're designing an automaton, you have to think about — as you're processing the input — what things you have to keep track of.
Vì vậy, nếu bạn đang thiết kế một người máy tự động, Bạn phải suy nghĩ về điều đó — trong quá trình xử lý dữ liệu đầu vào — những thứ bạn có để theo dõi.
And you're going to make a state for each one of those possibilities. OK? So you need to get comfortable with that.
Và bạn sẽ làm một trạng thái cho mỗi người trong số những khả năng đó. ĐƯỢC RỒI? Vì vậy, bạn cần phải có được Tôi thấy thoải mái với điều đó.
Let's look at another example, the language C where the inputs have an equal number of 0's and 1's. That turns out to be not a regular language.
Chúng ta hãy xem một ví dụ khác, ngôn ngữ C, trong đó các đầu vào có số lượng bằng nhau gồm toàn số 0 và số 1. Hóa ra là Không phải là ngôn ngữ chính quy.
So, in other words, what that means is there's no way to recognize that language with a finite automaton. You just can't do it. That's beyond the capabilities of finite automata.
Nói cách khác, điều đó có nghĩa là gì không có cách nào nhận ra ngôn ngữ đó với một máy tự động hữu hạn. Bạn không thể làm được điều đó. Điều đó vượt quá khả năng cho phép. của các automata hữu hạn.
And that's a statement we will prove later. OK.
Và đó là một tuyên bố. Chúng ta sẽ chứng minh điều đó sau. ĐƯỢC RỒI.
And our goal over the next lecture or so is to understand the regular languages, which you can do in a very comprehensive way. So we're going to start to do that now.
Và mục tiêu của chúng ta trong thời gian tới là... bài giảng tiếp theo hoặc gì đó là để hiểu quy luật ngôn ngữ, mà bạn có thể thực hiện một cách rất toàn diện. Vậy nên chúng ta sẽ Hãy bắt đầu làm điều đó ngay bây giờ.
So first, we're going to introduce this concept of regular expressions — which, again, these are things you may have run into in one way or another before.
Vậy trước tiên, chúng ta sẽ... giới thiệu khái niệm này các biểu thức chính quy — mà, một lần nữa, những điều này là những thứ bạn có thể đã gặp phải trong một Trước đây, bằng cách này hay cách khác.
So we're going to introduce something called the regular operations.
Vậy nên chúng ta sẽ giới thiệu một cái gì đó được gọi là các hoạt động thường quy.
Now, I'm sure you're familiar with the arithmetical operations, like plus and times. Those apply to numbers.
Giờ thì tôi chắc chắn rồi. bạn đã quen thuộc với các phép toán số học, như cộng và nhân. Điều đó áp dụng cho các con số.
The operations we're going to talk about are operations that apply to languages. So they're going to take, let's say, two languages, you apply an operation, you're going to get back another language.
Các hoạt động mà chúng tôi đang thực hiện sắp nói về là các hoạt động mà Áp dụng cho ngôn ngữ. Vậy nên họ sẽ lấy, Ví dụ, hai ngôn ngữ, bạn áp dụng một phẫu thuật, bạn sẽ đi để học lại một ngôn ngữ khác.
Like the union operation, for example, that's one you probably have seen before. The union of two languages here is a collection of strings that are in either one or the other.
Giống như công đoàn hoạt động, ví dụ, Đó là một điều mà bạn có lẽ Đã từng thấy trước đây. Sự kết hợp của hai Ngôn ngữ ở đây là một tập hợp các chuỗi hoặc là ở trong trường hợp này hoặc trường hợp kia.
But there are other operations, which you may not have seen before, that we're going to look at — the concatenation operation, for example.
Nhưng còn những điều khác nữa. hoạt động, mà Có thể bạn chưa từng thấy trước đây, mà chúng ta sẽ xem xét — sự nối ví dụ như hoạt động.
So that says you're going to take a string from the first language and another string from the second language and stick them together. And it's called concatenating them.
Vậy điều đó có nghĩa là bạn sẽ mang đi một chuỗi từ đầu tiên ngôn ngữ và một chuỗi khác từ ngôn ngữ thứ hai và dán chúng lại với nhau. Và nó được gọi là nối chúng lại với nhau.
And you do that in all possible ways, and you're going to get the concatenation language from these two languages that you're starting with, A and B. The symbol we use for concatenation is this little circle.
Và bạn làm điều đó trong tất cả các cách có thể, và bạn sẽ nhận được ngôn ngữ nối chuỗi từ hai ngôn ngữ này mà bạn đang bắt đầu với, A và B. Biểu tượng mà chúng ta dùng để nối chuỗi Đây là một vòng tròn nhỏ.
But often, we don't. We just suppress that and we write the two languages next to one another with the little circle implied. So this also means concatenation over here, just like this does.
Nhưng thường thì chúng ta không làm vậy. Chúng ta chỉ cần kìm nén điều đó và chúng tôi viết bằng hai ngôn ngữ cạnh nhau với Hình tròn nhỏ đó ám chỉ điều gì. Vậy điều này cũng có nghĩa là sự nối tiếp Ở đây, cũng giống như thế này.
And the last of the regular operations is the so-called star operation, which is a unary operation. It applies to just a single language.
Và cuối cùng là hoạt động thường xuyên đó là cái gọi là hoạt động ngôi sao, Đây là một phép toán một ngôi. Nó chỉ áp dụng cho một ngôn ngữ duy nhất.
And so what you do is now you're going to take — to get a member of the star language, you're going to take a bunch of strings in the original language, A, you stick them together.
Vậy nên điều bạn cần làm bây giờ là... Bạn sẽ lấy — để trở thành thành viên của ngôn ngữ của các vì sao, Bạn sẽ lấy một bó dây bằng ngôn ngữ gốc, A, bạn dán chúng lại với nhau.
Any number of members of A, you stick them together, and that becomes an element of the star language. And we'll do an example in a second if you didn't get that.
Bất kỳ số lượng thành viên nào của A, bạn dán chúng lại với nhau. và điều đó trở thành một yếu tố của ngôn ngữ sao. Và chúng ta sẽ làm một ví dụ trong phần sau. Thứ hai, nếu bạn chưa hiểu.
But one important element is that when you have the star language, you can also allow it to stick zero elements together, and then you get the empty string.
Nhưng có một yếu tố quan trọng là khi bạn có ngôi sao ngôn ngữ, bạn có thể cũng cho phép nó dính không có phần tử nào ở cùng nhau, và Sau đó bạn sẽ nhận được chuỗi rỗng.
So that's always a member of the star language, the empty string. OK, so let's look at some examples. Let's say A is the language — these are two strings here — good, bad.
Vậy nên đó luôn là một thành viên của ngôi sao Ngôn ngữ, chuỗi rỗng. Được rồi, vậy chúng ta cùng xem nhé. trong một số ví dụ. Giả sử A là ngôn ngữ — đây là Có hai luồng ý kiến ở đây - tốt, xấu.
And B is the language boy, girl.
Và B là ngôn ngữ dành cho bé trai, bé gái.
Now, if we take the union of those two, we get good, bad, boy, girl. That's kind of what you'd expect.
Bây giờ, nếu chúng ta lấy sự kết hợp của hai điều đó, Chúng ta có người tốt, người xấu, con trai, con gái. Đó là kiểu như vậy Đúng như bạn mong đợi.
And now let's take a look at the concatenation.
Và bây giờ chúng ta hãy cùng xem xét. tại điểm nối.
Now, if you concatenate the A and the B language, you're going to get all possible ways of having an A string followed by all possible ways of having a B string.
Bây giờ, nếu bạn nối chuỗi Ngôn ngữ A và ngôn ngữ B, Bạn sẽ nhận được tất cả các cách có thể để đạt điểm A chuỗi ký tự theo sau bởi tất cả các khả năng Các cách để có dây B.
So you can get goodboy, goodgirl, badboy, badgirl.
Vậy là bạn có thể trở thành một chú chó ngoan, Cô gái ngoan, chàng trai hư, cô gái hư.
Now, looking at the star, well, that applies to just one language. So let's say it's the good, bad language from A.
Bây giờ, nhìn vào ngôi sao, ừm, cái đó Chỉ áp dụng cho một ngôn ngữ duy nhất. Vậy giả sử đó là Ngôn ngữ tốt, ngôn ngữ xấu từ A.
And so the A star that you get from that is all possible ways of sticking together the strings from A. So using no strings, you always get the empty string.
Và vì vậy, ngôi sao hạng A những gì bạn nhận được từ đó tất cả các cách dính có thể cùng nhau các dây từ A. Vậy nên, không cần ràng buộc gì cả, bạn Luôn nhận được chuỗi rỗng.
That's always guaranteed to be a member of A. And then just taking one element of A, you get good, or another element, bad.
Điều đó luôn được đảm bảo. trở thành thành viên của A. Và sau đó chỉ cần lấy một phần tử của A, bạn trở nên giỏi, hoặc Một yếu tố khác, không tốt.
But now two elements of A, you get goodgood or goodbad, and so on. Or three elements of A, goodgoodgood, goodgoodbad.
Nhưng giờ đây, hai yếu tố của A, Bạn sẽ nhận được kết quả tốt hoặc tốt/xấu. vân vân. Hoặc ba phần tử của A, tốt tốt tốt, tốt tốt xấu.
And so, in fact, A star is going to be an infinite language if A itself contains any non-empty member.
Và thực tế, một ngôi sao là... sẽ trở thành một ngôn ngữ vô tận nếu bản thân A chứa bất kỳ thành viên nào không rỗng.
So if A is the empty language or if A contains just the language empty string, then A star will be not an infinite language. It'll just be the language empty string.
Vậy nếu A là tập hợp rỗng ngôn ngữ hoặc nếu A chứa chỉ là ngôn ngữ trống rỗng sợi dây, sau đó là một ngôi sao sẽ không phải là một Ngôn ngữ vô tận. Nó sẽ chỉ là Chuỗi rỗng trong ngôn ngữ.
But otherwise, it'll be an infinite language. I'm not even sure — OK. I'm not — [LAUGHS] I'm ignoring the chat here.
Nhưng nếu không thì sẽ là một ngôn ngữ vô tận. Tôi thậm chí còn không chắc nữa — ĐƯỢC RỒI. Tôi không phải — [CƯỜI] Tôi sẽ không tham gia vào cuộc trò chuyện này nữa.
I'm hoping people are getting — are you guys are getting your questions answered by our TAs? How are we doing, Thomas?
Tôi hy vọng mọi người bạn đang nhận được — bạn có phải không? các chàng trai đang lấy của bạn Bạn có câu hỏi nào được trợ giảng giải đáp không? Chúng ta đang làm tốt chứ, Thomas?
AUDIENCE
One question is, are the slides going to be posted?
Một câu hỏi là, liệu Các slide sẽ được đăng tải chứ?
MICHAEL SIPSER
Are the slides going to be posted? Well, the whole lecture is going to be recorded. Is it helpful to have the slides separately? I can post the slides.
Liệu Các slide sẽ được đăng tải chứ? Vâng, toàn bộ bài giảng Sẽ được ghi âm lại. Liệu việc có Các slide được tách riêng ra à? Tôi có thể đăng các slide lên.
Sure. Remind me if I don't, but I'll try to do that. Yes, it is helpful. I will do that.
Chắc chắn. Nhắc tôi nếu tôi quên nhé. Nhưng tôi sẽ cố gắng làm điều đó. Vâng, điều đó rất hữu ích. Tôi sẽ làm điều đó.
Yeah. Yeah, I will post the slides. Just, Thomas, it's your job to remind me.
Vâng. Vâng, tôi sẽ đăng các slide lên. Thomas à, đó là... Bạn có trách nhiệm nhắc nhở tôi.
AUDIENCE
OK.
Được rồi.
MICHAEL SIPSER
All right, good. So we talked about the regular operations. Let's talk about the regular expressions.
Được rồi, tốt. Vậy là chúng tôi đã nói chuyện về... hoạt động thường xuyên. Chúng ta hãy cùng nói về Biểu thức chính quy.
So regular expressions are — just like you have the arithmetical operations, then you can get arithmetical expressions, like 1 plus 3 times 7. So now we're going to make expressions out of these operations.
Vì vậy, bình thường biểu hiện chỉ là... giống như bạn có các phép toán số học, sau đó bạn có thể nhận được biểu thức số học, giống như 1 cộng 3 nhân 7. Vậy bây giờ chúng ta sẽ... thể hiện cảm xúc của các hoạt động này.
First of all, you have, the more atomic things, the building blocks of the expressions, which are going to be like elements of sigma, elements of the alphabet or the sigma itself as an alphabet symbol, or the empty language or the empty string.
Trước hết, bạn có, những thứ mang tính nguyên tử hơn, các khối cấu tạo của những biểu hiện đó sẽ giống như các yếu tố của sigma, các phần tử của bảng chữ cái hoặc chính sigma đó như một ký hiệu trong bảng chữ cái, hoặc ngôn ngữ trống rỗng hoặc chuỗi rỗng.
These are going to be the building blocks for the regular expressions. We'll do an example in a second. And then you combine those basic elements using the regular operations of union, concatenation, and star.
Đây sẽ là các khối xây dựng dành cho các biểu thức chính quy. Chúng ta sẽ xem một ví dụ ngay sau đây. Và sau đó bạn kết hợp những yếu tố cơ bản đó sử dụng các hoạt động thông thường của phép hợp, phép nối và phép sao.
So these are the atomic expressions, these are the composite expressions. So, for example, if you look at the expression 0 union 1 star — so we can also write that as sigma star.
Vậy đây là biểu thức nguyên tử, đây là các biểu thức phức hợp. Ví dụ, nếu bạn xem xét... biểu thức 0 hợp 1 sao — vậy nên chúng ta cũng có thể viết đó là ngôi sao sigma.
Because if sigma is 0 and 1, then sigma star is the same thing as 0 union 1 — sigma is the same as 0 union 1.
Vì nếu sigma bằng 0 và 1, sau đó là sao sigma cũng giống như 0 hợp 1 — sigma bằng 0 hợp 1.
And that just gives all possible strings over sigma. So this is something you're going to see frequently.
Và điều đó cho thấy tất cả Các chuỗi có thể có trên sigma. Vậy đây là điều mà bạn đang làm Sẽ thường xuyên gặp gỡ.
Sigma star means this is the language of all strings over the alphabet we're working with at that moment.
Sigma star nghĩa là đây là ngôn ngữ của tất cả các chuỗi trên bảng chữ cái chúng ta đang làm việc với ai vào thời điểm đó.
Now, if you take sigma star 1, you just concatenate 1 onto all of the elements of sigma star, and that's going to give you all strings that end with a 1.
Bây giờ, nếu bạn lấy sigma star 1, bạn chỉ nối 1 vào tất cả các yếu tố của sao sigma, và điều đó sẽ mang lại cho bạn tất cả các chuỗi kết thúc bằng số 1.
Technically, you might imagine writing this with braces around the 1, but generally, we don't do that.
Về mặt kỹ thuật, bạn có thể Hãy tưởng tượng việc viết điều này với dấu ngoặc vuông quanh số 1, nhưng Thông thường, chúng tôi không làm như vậy.
We just — single element sets, single element strings, we write without the braces, because it's clear enough without them, and it gets messy with them.
Chúng ta chỉ cần một yếu tố duy nhất tập hợp, chuỗi ký tự đơn, chúng tôi viết mà không có niềng răng, bởi vì nó là Đã đủ rõ ràng mà không cần đến chúng. Và mọi chuyện trở nên rắc rối với họ.
So sigma star 1 is all strings that end with 1. Or, for example, you take sigma star 11 sigma star, that is all strings that contain 11.
Vậy sigma star 1 là tất cả các chuỗi kết thúc bằng 1. Hoặc, ví dụ, bạn chọn Sigma Star 11 sigma star, chỉ vậy thôi. chuỗi chứa số 11.
And we already saw that language once before. That's the language of that other machine that we presented one or two slides back. OK?
Và chúng ta đã thấy điều đó rồi. Ngôn ngữ đã từng được sử dụng trước đây. Đó là ngôn ngữ của cái máy kia mà chúng tôi đã trình bày một hoặc hai slide trước đó. ĐƯỢC RỒI?
Right.
Phải.
Yeah, but in terms of readings — by the way, sorry, I don't know if it's helpful to you for me to do these interjections — but the readings are listed also on the homework.
Đúng vậy, nhưng xét về mặt... các bài đọc — nhân tiện, Xin lỗi, tôi không biết. Nếu điều đó có ích cho bạn để tôi làm những việc này thán từ — nhưng các bài đọc được liệt kê Cũng có trong bài tập về nhà.
So if you look at the posted homework 1, it tells you which chapters you should be reading now.
Vì vậy, nếu bạn nhìn vào Bài tập về nhà số 1 đã được đăng tải. Nó cho bạn biết những chương nào Bạn nên đọc ngay bây giờ.
And also, if you look at the course schedule, which is also on the home page, it has the whole course plan and which readings are for which dates.
Và nếu bạn nhìn vào... lịch trình khóa học, cũng là Trên trang chủ, nó có toàn bộ kế hoạch khóa học và cái nào Các bài đọc dành cho những ngày nào?
So it's all there for you.
Vậy là mọi thứ đều có sẵn cho bạn.
And so our goal here — this is not an accident that sigma star 11 sigma star happens to be the same language as we saw before from the language of that finite automaton M1.
Và vì vậy, mục tiêu của chúng ta ở đây là — Đây không phải là sự tình cờ. ngôi sao sigma 11 ngôi sao sigma xảy ra là cùng một ngôn ngữ như chúng ta đã thấy trước đây từ ngôn ngữ của máy tự động hữu hạn M1 đó.
In fact, that's a general phenomenon. Anything you can do with a regular expression, you can also do with a finite automaton and vice versa.
Thực tế, đó là một hiện tượng chung. Bất cứ điều gì bạn có thể làm với một biểu thức chính quy, Bạn cũng có thể làm điều đó với một số hữu hạn. người máy và ngược lại.
They are equivalent in power with respect to the class of languages they describe. And we'll prove that.
Chúng tương đương nhau có quyền lực và được tôn trọng cho lớp học của Những ngôn ngữ mà chúng mô tả. Và chúng ta sẽ chứng minh điều đó.
OK?
ĐƯỢC RỒI?
So if you step back for a second and just let yourself appreciate this, it's kind of an amazing thing.
Vì vậy, nếu bạn lùi lại một bước đợi một giây và cứ để Bạn hãy tự mình đánh giá cao điều này, Đó quả là một điều tuyệt vời.
Because finite automata, with the states and transitions, and the regular expressions, with these operations of union, concatenation, and star, they look totally different from one another.
Bởi vì máy tự động hữu hạn, với các trạng thái và sự chuyển đổi, và các biểu thức chính quy, với các hoạt động liên hiệp này, sự nối tiếp và ngôi sao, Chúng trông hoàn toàn khác nhau. từ nhau.
They look like they have nothing to do with one another. But, in fact, they both describe exactly the regular languages, the same class of languages.
Trông chúng có vẻ như vậy. Không liên quan gì đến nhau cả. Nhưng trên thực tế, cả hai đều mô tả Chính xác là các ngôn ngữ thông thường, cùng một loại ngôn ngữ.
And so it's kind of a cool fact that you can prove, that these two very different looking systems actually are equivalent to one another.
Và vì vậy, nó khá thú vị. sự thật mà bạn có thể chứng minh được, hai người này rất các hệ thống có vẻ ngoài khác nhau thực chất là tương đương với nhau.
Can we get empty string from empty set? Yeah. There are a bunch of exotic cases, by the way. So empty language star is the language which has just the empty string.
Chúng ta có thể trống không? chuỗi từ tập hợp rỗng? Vâng. Có rất nhiều Nhân tiện, đây là những trường hợp hiếm gặp. Ngôn ngữ trống rỗng như sao là ngôn ngữ mà Chỉ chứa chuỗi rỗng.
If you don't get that, chew on that one. But that is true.
Nếu bạn không hiểu điều đó, Hãy suy nghĩ kỹ về điều đó. Nhưng đó là sự thật.
OK, let's move on. OK, let's talk about closure properties now.
Được rồi, chúng ta tiếp tục thôi. Được rồi, chúng ta hãy nói về Các đặc tính đóng cửa hiện tại.
We're going to start doing something that has a little bit more meat to it, in terms of we're going to have our first theorem of the course coming here.
Chúng ta sẽ bắt đầu làm một thứ gì đó có một chút Còn nhiều chi tiết hơn nữa, xét về khía cạnh chúng ta Chúng ta sẽ có định lý đầu tiên. của khóa học sắp diễn ra ở đây.
And this is not a baby theorem. This is actually — there's going to be some meat to this. And you're going to have to not totally — this is not a toy.
Và đây không phải là một định lý sơ đẳng. Thực ra thì... có Sẽ có nhiều nội dung hấp dẫn trong phần này. Và bạn sẽ không hoàn toàn — Đây không phải là đồ chơi.
We're proving something that has real substance.
Chúng ta đang chứng minh điều gì đó Điều đó thực sự có giá trị.
And the statement of this theorem says that the regular languages are closed, that really, the class of regular languages are closed under union, closed under the union operation.
Và tuyên bố của định lý này nói rằng các ngôn ngữ thông thường Chúng đã đóng cửa, thật vậy. lớp các ngôn ngữ chính quy đóng cửa theo quy định của công đoàn, đã đóng cửa dưới sự điều hành của công đoàn.
So what do I mean by that?
Vậy ý tôi muốn nói là gì?
So when you say a collection of objects is closed under some operation, that means applying that operation to those objects leaves you in the same class of objects.
Vậy nên khi bạn nói một tập hợp các đối tượng đã đóng cửa theo một số hoạt động, đó có nghĩa là áp dụng điều đó thao tác đối với các đối tượng đó khiến bạn ở trong cùng loại đối tượng.
Like the positive integers, the natural numbers, that's closed under addition.
Giống như các số nguyên dương, các số tự nhiên, Điều đó đã được đóng lại theo phép cộng.
Because when you add two positive integers, you get back a positive integer. But they're not closed under subtraction. Because 2 minus 4, you get something which is not a positive integer.
Bởi vì khi bạn thêm hai số nguyên dương, Bạn sẽ nhận lại một số nguyên dương. Nhưng chúng không đóng cửa. dưới phép trừ. Vì 2 trừ 4, bạn lấy thứ gì đó không phải là số nguyên dương.
So closed means you leave yourself in the collection.
Vậy đóng cửa có nghĩa là bạn rời đi Hãy đưa chính bạn vào bộ sưu tập.
And the fact is that if you look at all the regular languages — these are the languages that the finite automata can recognize — they are closed under the union operation.
Và sự thật là nếu bạn nhìn vào... bằng tất cả các ngôn ngữ thông thường — Đây là những ngôn ngữ mà Máy tự động hữu hạn có thể nhận biết — Chúng bị đóng cửa theo hoạt động của công đoàn.
So if you start off with two regular languages and you apply the union, you get back another regular language. And that's what the statement of this theorem is.
Vậy nếu bạn bắt đầu với hai ngôn ngữ chính quy và bạn áp dụng công đoàn, bạn sẽ nhận được trở lại một ngôn ngữ thông thường khác. Và đó là điều mà Phát biểu của định lý này là.
I hope that's clear enough in the way I've written it. If A1 and A2 are regular, then A1 union A2 is also regular. That's what the statement of this is.
Tôi hy vọng điều đó đủ rõ ràng. theo cách tôi đã viết. Nếu A1 và A2 đều là số thường thì Công đoàn A1 A2 cũng là công đoàn thường. Đó là những gì Lời tuyên bố này là.
And it's just simply that — that's proving that the class of regular language is closed under union. So we're going to prove that. So how do you prove such a thing?
Và đơn giản chỉ là như vậy thôi — Điều đó chứng minh rằng lớp ngôn ngữ chính quy Đóng cửa do công đoàn. Vì vậy, chúng ta sẽ chứng minh điều đó. Vậy bạn làm thế nào? Chứng minh điều đó?
So the way we're going to prove that is you start off with what we're assuming. So our hypothesis is that we have two regular languages.
Vậy nên, theo cách chúng ta đang đi để chứng minh đó là bạn bắt đầu với điều gì Chúng ta đang giả định như vậy. Vậy giả thuyết của chúng tôi là chúng ta có hai ngôn ngữ chính quy.
And we have to prove our conclusion, that the union is also regular. Now, the hypothesis that they're regular, you have to unpack that and understand, what does that get you?
Và chúng ta phải chứng minh Kết luận của chúng tôi, Công đoàn đó cũng hoạt động thường xuyên. Bây giờ, giả thuyết Chúng là những thứ bình thường, bạn phải giải nén nó và Tôi hiểu, điều đó có nghĩa là gì? Bạn hiểu chứ?
And them being regular means that there are finite automata that recognize those languages. So let's give those two finite automata names.
Và việc chúng là những phương tiện thông thường rằng có các automata hữu hạn những ngôn ngữ đó được nhận biết. Vậy hãy trao hai cái đó cho hai người đó. Tên của các automata hữu hạn.
So M1 and M2 are the two final automata that recognize those two languages, A1 and A2. That's what it means, that they're regular, that these automata exist.
Vậy M1 và M2 là hai máy tự động cuối cùng nhận ra hai điều đó Ngôn ngữ, A1 và A2. Đó là ý nghĩa của nó. Chúng là những thứ bình thường, Rằng những cỗ máy tự động này tồn tại.
So let's have those two automata, M1 and M2, using the components as we've described, the respective state sets, input alphabet, transition functions, the two starting states and the two collections of accepting states.
Vậy hãy lấy hai cái đó đi. máy tự động, M1 và M2, sử dụng các thành phần như chúng ta đã được mô tả, trạng thái tương ứng tập hợp, nhập bảng chữ cái, hàm chuyển đổi, hai trạng thái ban đầu và hai các bộ sưu tập chấp nhận các tiểu bang.
Here I'm assuming that they're over the same alphabet. You could have automata which operate over different alphabets. It's not interesting to do that. It doesn't add anything.
Ở đây tôi giả định rằng chúng là trên cùng một bảng chữ cái. Bạn có thể đã các máy tự động hoạt động trên các bảng chữ cái khác nhau. Làm vậy không thú vị chút nào. Nó chẳng thêm được gì cả.
The proof would be exactly the same. So let's just not overcomplicate our lives and focus on the more interesting case, so assuming that the two input alphabets are going to be the same.
Bằng chứng sẽ là Hoàn toàn giống nhau. Vậy nên, chúng ta đừng làm mọi thứ trở nên quá phức tạp. cuộc sống và trọng tâm của chúng ta về những điều thú vị hơn trường hợp đó, vì vậy giả sử hai bảng chữ cái đầu vào Chúng sẽ vẫn như vậy.
And from these two automata, we have to show that this language here, the union, is also a regular language. And we're going to do that by constructing the automaton which recognizes the union.
Và từ hai người này chúng ta có các máy tự động để chứng minh điều này Ngôn ngữ ở đây, liên hiệp, cũng là một ngôn ngữ chính quy. Và chúng ta sẽ làm điều đó. bằng cách chế tạo máy tự động công nhận liên hiệp đó.
That's really the only thing that we can do. So we're going to build an automaton out of M1 and M2 which recognizes the union language A1 union A2.
Đó thực sự là điều duy nhất điều mà chúng ta có thể làm. Vậy nên chúng ta sẽ xây dựng một người máy từ M1 và M2 công nhận liên hiệp Ngôn ngữ A1 liên hiệp A2.
And the task of M is that it should accept its input if either M1 or M2 accept.
Và nhiệm vụ của M là... Nó nên chấp nhận đầu vào của nó nếu M1 hoặc M2 chấp nhận.
And now what I'd like you to think about doing that, how in the world are we going to come up with this finite automaton M?
Và bây giờ tôi sẽ làm gì bạn nghĩ như vậy về việc làm đó, Làm sao mà lại như thế được chứ? Chúng ta sẽ đưa ra máy tự động hữu hạn M này?
And the way we do that is to think about, how would you do that union language?
Và cách chúng tôi làm điều đó là để suy nghĩ về điều đó, thì sẽ như thế nào Bạn dùng ngôn ngữ công đoàn đó à?
If I ask you — I give you two automata, M1 and M2, and I say, here's an input, w.
Nếu tôi hỏi bạn — Tôi tặng bạn hai cỗ máy tự động, M1 và M2, và tôi nói, Đây là dữ liệu đầu vào, w.
Is w in the union language? That's the job that M is supposed to solve. And I suggest you try to figure out how you would solve it first.
Liệu chữ w có nằm trong ngôn ngữ của công đoàn không? Đó là công việc của M. được cho là sẽ giải quyết vấn đề này. Và tôi đề nghị bạn cố gắng tìm hiểu Bạn sẽ giải quyết nó như thế nào trước tiên?
I mean, this is a good strategy for solving a lot of the problems in this course. Put yourself in the place of the machine you're trying to build.
Ý tôi là, đây là một điều tốt. chiến lược để giải quyết nhiều vấn đề về các vấn đề trong khóa học này. Hãy đặt mình vào vị trí của người khác. Cỗ máy mà bạn đang cố gắng chế tạo.
And so if you want to try to figure out how to do that, a natural thing is, well, you take w, you feed it into M1, and then you feed it into M2.
Vì vậy, nếu bạn muốn thử Tìm cách thực hiện điều đó, Một điều tự nhiên là, à, chính bạn. Lấy w, rồi đưa nó vào M1. và sau đó bạn đưa nó vào M2.
And if M1 accepts it, great, then you know it's in the union. And if not, you try it out in M2 and see if M2 accepts it.
Và nếu M1 chấp nhận Tuyệt vời, vậy thì bạn Tôi biết nó nằm trong công đoàn. Và nếu không được, bạn hãy thử xem sao. Nhấp vào M2 và xem M2 có chấp nhận không.
Now, you have to be a little careful, because you want to have a strategy that you can also implement in a finite automaton.
Bây giờ, bạn phải cẩn thận một chút, vì bạn muốn có một chiến lược mà bạn cũng có thể Triển khai trong một máy tự động hữu hạn.
And a finite automaton only gets one shot at looking at the input. You can't sort of rewind the input.
Và một máy tự động hữu hạn chỉ có một cơ hội khi xem xét dữ liệu đầu vào. Bạn không thể nào... Tua lại đầu vào.
You feed it first into M1 and then you feed it into M2 and operate in a sequential way like that. That's not going to be allowed in the way finite automata work.
Bạn đưa nó vào M1 trước. và sau đó bạn đưa nó vào M2. và hoạt động trong một theo trình tự như vậy. Điều đó sẽ không được phép. theo cách thức của máy tự động hữu hạn công việc.
So you're going to have to take it to the next level, be a little bit more clever.
Vì vậy, bạn sẽ phải Đưa nó lên một tầm cao mới, Hãy thông minh hơn một chút.
And instead of feeding it first into M1 and then and then into M2, you feed them into both in parallel.
Và thay vì cho ăn Đầu tiên nó được đưa vào M1 và sau đó vào M2, bạn cung cấp cho chúng vào cả hai song song.
So you take M1 and M2, and you run them both in parallel on the input w, keeping track of which state each of those two automata are in.
Vậy bạn lấy M1 và M2, và bạn chạy chúng cả hai đều hoạt động song song ở đầu vào w, theo dõi trạng thái nào mỗi hai người đó Chế độ tự động có tính năng đó.
And then at the end, you see if either one of those machines is in an accepting state, and then you accept.
Và rồi cuối cùng, bạn sẽ thấy nếu một trong hai máy đó đang trong trạng thái chấp nhận. và sau đó bạn chấp nhận.
So that's the strategy we're going to employ in building the finite automaton M out of M1 and M2. So in terms of a picture, here's M1 and M2.
Vậy đó là chiến lược mà chúng ta đang theo đuổi để sử dụng trong việc xây dựng hữu hạn Người máy M được tạo ra từ M1 và M2. Vậy nên, xét về mặt hình ảnh, Đây là M1 và M2.
Here is the automaton we're trying to build. We don't know how it's going to look like yet.
Đây là người máy tự động Chúng tôi đang cố gắng xây dựng. Chúng ta không biết nó như thế nào. Nó sẽ trông như thế nào nhỉ?
And yeah, so kind of getting ahead of myself, but here is a strategy, as I just described, for M.
Và vâng, đại loại là... Tôi hơi vội vàng, nhưng đây đó là một chiến lược, như tôi Vừa mô tả xong, dành cho M.
M is going to keep track of which state that M1 is in and which state M2 is in at any given moment.
M sẽ theo dõi trong đó nêu rằng M1 nằm trong và M2 thuộc bang nào tại bất kỳ thời điểm nào.
As we're reading the symbols of w, we're going to feed that into M1 and also into M2.
Khi chúng ta đang đọc các ký hiệu của w, chúng ta sẽ cho nó ăn vào M1 và cả vào M2.
And so the possibilities we have to keep track of in M are all the pairs of states that are in M1 and M2, because you're going to really be tracking M1 and M2 simultaneously.
Và do đó, những khả năng mà chúng ta có thể đạt được là... phải theo dõi trong M tất cả các cặp trạng thái những thứ nằm trong M1 và M2, vì bạn sắp đi để thực sự theo dõi M1 và M2 đồng thời.
So you have to remember which state M1 is in and also which state M2 is in.
Vì vậy bạn phải nhớ M1 đang ở tiểu bang nào và cũng M2 đang ở tiểu bang nào.
And so that really corresponds to what pair of states to remember, one from M1 and one from M2, and that's why I've indicated it like that.
Và điều đó thực sự tương ứng. với cặp quốc gia nào Để nhớ lại, một người từ M1 và một cái từ M2, đó là Lý do tôi nói như vậy.
So M1 is in state q, M2 is in state r at some given point in time. And that's going to correspond to M being in the pair q comma r.
Vậy M1 đang ở trạng thái q, M2 đang ở trạng thái r vào một thời điểm nhất định. Và điều đó sẽ tương ứng với M nằm trong cặp q phẩy r.
That's just the label of this particular state of m that we're going to apply here. OK?
Đó chỉ là nhãn mác của trạng thái cụ thể này của m mà chúng ta sẽ áp dụng ở đây. ĐƯỢC RỒI?
And then M is going to accept if either M1 and M2 is an accepting state.
Và sau đó M sẽ đi chấp nhận nếu một trong hai M1 và M2 là một trạng thái chấp nhận.
So it's going to be if either q or r is an accepting state, we're going to make this into an accepting state too. OK? Whoops. There we go.
Vậy nên, câu hỏi đặt ra là liệu một trong hai trường hợp nào sẽ xảy ra. q hoặc r là trạng thái chấp nhận, Chúng ta sẽ làm điều này cũng bước vào trạng thái chấp nhận. ĐƯỢC RỒI? Ối. Vậy là xong.
So let's describe this formally instead of by a picture, because we can do it both ways. And sometimes it's better to do it one way and sometimes the other way.
Vậy chúng ta hãy mô tả thay vào đó chính thức là bởi vì Chúng ta có thể làm theo cả hai cách. Và đôi khi thì tốt hơn là làm theo một cách và đôi khi theo hướng ngược lại.
So now if we take — the components of M now are the pairs of states from M1 and M2.
Vậy bây giờ nếu chúng ta lấy — Các thành phần của M hiện nay là Các cặp trạng thái từ M1 và M2.
Again, I'm writing this out literally, explicitly here, but you should make sure you're comfortable with this cross product notation.
Tôi viết lại điều này một lần nữa. Theo nghĩa đen, rõ ràng ở đây, nhưng bạn nên chắc chắn bạn cảm thấy thoải mái với ký hiệu tích chéo này.
So this is the collection of pairs of states, q1 and q2, where q1 is in the state of the first machine, q2 is the state of the second machine.
Đây là bộ sưu tập của các cặp trạng thái, q1 và q2, trong đó q1 nằm trong trạng thái của chiếc máy đầu tiên, q2 là trạng thái của máy thứ hai.
The start state is you start at the two start states of the two machines. So this is q1, q2 — probably I should have not reused the Q notation.
Trạng thái ban đầu là bạn bắt đầu từ điểm bắt đầu thứ hai trạng thái của hai máy. Vậy đây là q1, q2 — có lẽ tôi nên làm thế Không sử dụng lại ký hiệu Q.
I should have called these r's — now that I'm looking at that. But, anyway, I hope you're not confused by reusing this.
Lẽ ra tôi nên gọi những thứ này là chữ r — Bây giờ tôi mới nhận ra điều đó. Nhưng dù sao thì, tôi hy vọng bạn khỏe. Không gây nhầm lẫn khi tái sử dụng cái này.
q1 and q2 here are the specific start states of the two machines. These are just two other states, representative states of those machines.
q1 và q2 ở đây là trạng thái bắt đầu cụ thể của hai máy. Đây chỉ là hai ví dụ khác các tiểu bang, các tiểu bang đại diện của những cỗ máy đó.
Now, the transition function for the new machine is going to be built out of the transition functions from the previous machines.
Giờ là lúc chuyển đổi chức năng cho máy mới sẽ được xây dựng. của các hàm chuyển đổi so với các máy móc trước đó.
So when I have a pair, q, r, and I have the symbol a, where do we go? Which new pair do we get?
Vậy nên khi tôi có một cặp, q, r, và tôi có ký hiệu a, Chúng ta sẽ đi đâu? Chúng ta sẽ nhận được đôi giày mới nào?
Well, we just update the state from M1 and update the state from M2 according to their respective transition functions, and that's what's shown over here.
Vâng, chúng tôi vừa cập nhật trạng thái từ M1 và cập nhật trạng thái từ M2 theo đến các khu vực tương ứng của họ hàm chuyển đổi, và đó là điều được hiển thị ở đây.
Now let's take a look at the accepting states for M.
Bây giờ chúng ta hãy cùng xem xét các tiểu bang chấp nhận M.
The natural thing to do is look at the set of pairs of states, where we have a pair of states — a pair of accepting states, one from the first machine and one from the second machine.
Điều tự nhiên nhất là nhìn tại tập hợp các cặp trạng thái, nơi chúng ta có một cặp tiểu bang — một cặp quốc gia chấp nhận, một trong những máy đầu tiên và một cái từ máy thứ hai.
But if you're thinking with me, you realize that this is not the right thing.
Nhưng nếu bạn Bạn đang nghĩ cùng tôi, bạn nhận ra rằng đây là Không phải là điều đúng đắn.
What is DFAs?
DFA là gì?
Did I would call them DFA somewhere? Oh, somebody else is probably doing that in the chat. The DFA — careful what notation you're using. We haven't introduced DFAs yet.
Tôi có nên gọi điện không? Họ có DFA ở đâu đó không? Ồ, chắc là người khác rồi. Làm điều đó trong phần trò chuyện. Bộ Ngoại giao Philippines (DFA) - hãy cẩn thận với những gì... ký hiệu bạn đang sử dụng. Chúng tôi chưa giới thiệu DFA.
We'll do that next on Thursday. But these are DFAs. These are just finite automata, Deterministic Finite Automata. That's why the D.
Chúng ta sẽ làm việc đó vào thứ Năm tới. Nhưng đây là các DFA. Đây chỉ là các automata hữu hạn. Máy tự động hữu hạn xác định. Đó là lý do tại sao chữ D.
Anyway, so this is actually not right, because if you think about what this is saying, it says that both components have to be accepting. And you want either one to be accepting.
Tóm lại, đây là... Thực ra không đúng. bởi vì nếu bạn nghĩ Về ý nghĩa của điều này, Nó nói rằng cả hai thành phần đều như nhau Phải biết chấp nhận. Và bạn muốn một trong hai điều đó. Một điều cần có là sự chấp nhận.
So this is not good. This would be the wrong way of defining it. That actually gives the intersection language.
Vậy nên điều này không tốt. Đây sẽ là một sai lầm. cách định nghĩa nó. Điều đó thực sự mang lại Ngôn ngữ giao nhau.
And really, kind of along the way, it's proving closure under intersection, which we don't care about but might be useful to have in our back pocket sometime in the future.
Và thực sự, tốt bụng trên đường đi, Nó đang chứng tỏ sự kết thúc. dưới giao lộ, mà chúng ta không quan tâm về nhưng có thể Sẽ rất hữu ích khi mang theo bên mình. bỏ túi vào một thời điểm nào đó trong tương lai.
In order to get closure under a union, we have to write it this slightly more complicated looking way, which says the pair, what you want to have is either the first state is an accepting state and then any state for the second element, or any state for the first element and an accepting state for the second element.
Để có được đóng cửa dưới sự quản lý của công đoàn, chúng ta phải viết nó như thế này phức tạp hơn một chút nhìn theo hướng đó, điều đó cho thấy Cặp đôi, điều bạn muốn có là hoặc trạng thái đầu tiên là một trạng thái chấp nhận và sau đó bất kỳ tiểu bang nào cho yếu tố thứ hai, hoặc bất kỳ tiểu bang nào cho yếu tố đầu tiên và một trạng thái chấp nhận cho phần tử thứ hai.
That's what it means to have the union, to be doing the union. OK? So let's do — oh, here's a quick check-in.
Đó chính là ý nghĩa của việc sở hữu Công đoàn, để thực hiện công đoàn. ĐƯỢC RỒI? Vậy chúng ta hãy làm — ồ, Đây là thủ tục nhận phòng nhanh.
So let's do another poll here. We thought we were done with these.
Vậy chúng ta hãy tiến hành một cuộc thăm dò ý kiến khác. Chúng tôi nghĩ rằng chúng tôi là Xong với những thứ này rồi.
Again — oh, here we go. So it was too complicated to write it out in the polls, so I actually put it up on the slide for you.
Lại nữa rồi— ôi, lại bắt đầu thôi. Vì vậy, nó quá phức tạp để Hãy ghi điều đó vào các cuộc thăm dò ý kiến. Vì vậy, tôi đã thực sự đăng nó lên. Trên slide dành cho bạn.
So all I'm asking is that if M1 has k1 states and M2 has k2 states, how many states does M have?
Vậy điều tôi muốn hỏi là nếu M1 có k1 trạng thái và M2 có k2 trạng thái, như thế nào M có bao nhiêu tiểu bang?
Is it the sum, the sum of the squares, or the product?
Có phải đó là tổng, tổng của Bình phương hay tích?
OK, you have to think about the states of M, what do they look like? And come on, guys.
Được rồi, bạn phải suy nghĩ Về các trạng thái của M, điều gì Chúng trông như thế nào? Thôi nào các bạn.
All right, ending the poll, sharing results. Yes, indeed, it is — most of you got it correct. It is C, the product.
Được rồi, kết thúc Khảo sát và chia sẻ kết quả. Vâng, đúng vậy - hầu hết tất cả các bạn đều trả lời đúng. Đó là C, là sản phẩm.
Because when you look at the number of pairs of states from M1 and M2, you need all possible pairs.
Bởi vì khi bạn nhìn vào số lượng các cặp trạng thái từ M1 và M2, bạn Cần tất cả các cặp có thể.
And so it's the number of states in M1 times the number of states in M2. So make sure you understand that and think about that so that you're following and get this.
Và vì vậy, đó là số lượng của các tiểu bang trong M1 lần số lượng của các tiểu bang trong M2. Vì vậy, hãy chắc chắn rằng bạn hiểu và hãy suy nghĩ về điều đó để bạn Theo dõi và nhận được điều này.
All right, so let's move on here. So we have another five minutes or so. Let's start thinking about closure under concatenation.
Được rồi, vậy thì Chúng ta hãy chuyển sang vấn đề khác. Vậy là chúng ta có thêm một cái nữa. Khoảng năm phút. Chúng ta hãy bắt đầu suy nghĩ về Đóng lại dưới phép nối chuỗi.
So if we have two regular languages, so is the concatenation language. We're going to try to prove that. We won't finish, but we'll at least get our creative juices going about it.
Vậy nếu chúng ta có hai ngôn ngữ chính quy, vậy Ngôn ngữ nối chuỗi. Chúng ta sẽ Hãy thử chứng minh điều đó. Chúng ta sẽ không hoàn thành, nhưng chúng ta sẽ... ít nhất cũng khơi dậy nguồn cảm hứng sáng tạo của chúng ta thực hiện điều đó.
So we're going to do the same scheme here. We're going to take two machines for A1 and A2 and build a machine for the concatenation language out of those two.
Vậy nên chúng ta sẽ làm Phương án ở đây cũng tương tự. Chúng ta sẽ lấy hai cái. máy móc cho A1 và A2 và chế tạo một cỗ máy cho ngôn ngữ nối ngoài Trong hai người đó.
So here are the two machines for A1 and A2 written down. And now here is the concatenation language.
Vậy đây là hai chiếc máy. Đối với A1 và A2 được viết ra. Và bây giờ đây là Ngôn ngữ nối chuỗi.
And I'm going to propose to you a strategy — which is not going to work, but it still is going to be a good intuition to have.
Và tôi sẽ đề xuất Một chiến lược dành cho bạn — điều đó sẽ không xảy ra để làm việc, nhưng nó vẫn Sẽ là một điều tốt Trực giác cần có.
So what I'm going to do is I'm going to make a copy of — OK, let's understand what M is supposed to do first. So M should accept its input.
Vậy nên điều tôi sẽ làm là Tôi sẽ sao chép cái này — Được rồi, chúng ta hãy cùng tìm hiểu điều đó. M đáng lẽ phải làm trước. Vì vậy, M nên chấp nhận đầu vào của nó.
So think about this. M is doing the concatenation language. So it's given a string. And it has to answer, is it in the concatenation language A1A2 or not?
Hãy suy nghĩ về điều này. M đang làm điều đó Ngôn ngữ nối chuỗi. Vậy là nó được cung cấp một chuỗi ký tự. Và nó phải trả lời, liệu nó có phải vậy không? trong ngôn ngữ nối chuỗi A1A2 hay không?
So it should accept it if there's some way to divide w into two pieces where M1 accepts the first piece and M2 accepts the second piece. So here would be the picture.
Vì vậy, nó nên chấp nhận điều đó nếu có cách nào đó để chia w chia thành hai phần, trong đó M1 chấp nhận mảnh đầu tiên và M2 chấp nhận mảnh thứ hai. Đây là bức tranh.
OK? And now we have to try to make a machine which is going to solve this intuition. So how would you do that yourself? I'm giving you w.
ĐƯỢC RỒI? Và bây giờ chúng ta phải cố gắng chế tạo một cỗ máy có chức năng Tôi sẽ giải quyết trực giác này. Vậy bạn sẽ làm thế nào? Bạn tự làm việc đó à? Tôi đang đưa cho bạn chữ w.
And you can simulate M1 and M2.
Và bạn có thể mô phỏng M1 và M2.
So the natural thing is you're going to start out by simulating M1 for a while and then shift into simulating M2 for a while, because that's what's supposed to be happening as you're processing the input.
Vậy nên điều tự nhiên là... bạn sẽ đi để bắt đầu bằng mô phỏng M1 trong một thời gian và sau đó chuyển sang mô phỏng M2 trong một thời gian, bởi vì đó là điều được cho là đang xảy ra trong quá trình xử lý dữ liệu đầu vào.
So I'm going to suggest that in terms of the diagram like this. So we have here M1 and M2 copied here.
Vì vậy, tôi sẽ đề xuất rằng trong về mặt sơ đồ như thế này. Vậy chúng ta có M1 ở đây. và M2 được sao chép ở đây.
And what I propose doing is connecting M1 to M2 so that when M1 has accepted its input, we're going to jump to M2, because that's perhaps the first part of w.
Và điều tôi đề xuất làm là... đang kết nối M1 với M2 để khi M1 có đã chấp nhận ý kiến đóng góp của nó, chúng ta sẽ chuyển sang phần tiếp theo. M2, bởi vì đó có lẽ là phần đầu của w.
And now we're going to have M2 process the second part of w.
Và bây giờ chúng ta sẽ có M2. xử lý phần thứ hai của w.
So the way I'm going to implement that is by declassifying the start state of M2, having transition symbols from the accepting states of M1 to M2, and then removing these guys here as accepting states.
Vậy nên, theo cách tôi đang làm... sẽ triển khai tức là bằng cách giải mật trạng thái ban đầu của M2, có các ký hiệu chuyển đổi từ các trạng thái chấp nhận của M1 đến M2, và sau đó loại bỏ những thứ này Các bạn ở đây chấp nhận các tiểu bang.
And we would have to figure out what sort of labels to apply here. But, actually, this reasoning doesn't work. It's tempting, but flawed. Because — what goes wrong?
Và chúng ta sẽ phải tìm ra cách tìm hiểu xem loại nhãn nào Ứng tuyển tại đây. Nhưng thực ra, điều này Lý luận như vậy không hiệu quả. Điều đó nghe có vẻ hấp dẫn, nhưng lại có nhược điểm. Bởi vì— điều gì đã xảy ra sai sót?
What happens is that — it might be that when M1 has accepted an initial part of w and then it wants M2 to accept the rest, it might fail because M2 doesn't accept the rest.
Điều xảy ra là — có thể là khi M1 có chấp nhận một phần ban đầu của w và sau đó nó muốn M2 chấp nhận phần còn lại, Nó có thể thất bại vì M2 Không chấp nhận những điều còn lại.
And what you might have been better off doing is waiting longer in M1, because there might have been some other later place to split w, which is still valid.
Và những gì bạn có thể có sẽ tốt hơn nếu làm đang chờ đợi lâu hơn ở M1, bởi vì ở đó có thể là một số địa điểm khác sau này để chia w, cái nào vẫn còn hiệu lực.
Splitting w in the first place where you have M1 accepting an initial part may not be the optimal place to split w.
Chia w trong nơi đầu tiên ở đâu bạn có M1 chấp nhận phần ban đầu có thể không phải là phương án tối ưu nơi để chia tay.
You might want to wait later, and then you'll have a better chance of accepting w. So I'm not sure if you quite follow that. But, in fact, it doesn't work.
Bạn có thể muốn đợi sau đó, và rồi bạn sẽ có cơ hội tốt hơn chấp nhận w. Vậy nên tôi không chắc liệu Bạn hoàn toàn hiểu điều đó. Nhưng thực tế thì nó không hiệu quả.
The question is where to split w, and it's challenging, because how do you know where to split w? Because it depends upon what — it depends on y, and you haven't seen y yet.
Câu hỏi là nơi chia w, và điều đó thật khó khăn. vì sao bạn... Biết nên chia ở đâu không? Vì nó phụ thuộc vào điều gì — nó phụ thuộc vào y, và Bạn chưa gặp bạn.
So when you try to think about it that way, it looks hopeless. But, in fact, it's still true. And we'll see how to do that on Thursday.
Vì vậy, khi bạn cố gắng suy nghĩ về Nhìn theo cách đó, có vẻ như vô vọng. Nhưng trên thực tế, điều đó vẫn đúng. Và chúng ta sẽ xem cách làm thế nào Hãy làm việc đó vào thứ Năm.
So just to recap what we did today, we did our introductory stuff, we defined finite automata, regular languages. We defined the regular operations and expressions.
Tóm lại là như vậy. Những gì chúng ta đã làm hôm nay, chúng tôi đã làm những điều cơ bản, chúng ta đã định nghĩa các automata hữu hạn, ngôn ngữ chính quy. Chúng tôi đã định nghĩa quy tắc thông thường các phép toán và biểu thức.
We showed that the regular languages are closed under union. We started closure under intersection, to be continued.
Chúng tôi đã chứng minh rằng ngôn ngữ thông thường Các cơ sở này đóng cửa do công đoàn quản lý. Chúng tôi bắt đầu đóng cửa vào thời điểm đó. Giao lộ, tiếp tục.
Giấy phép mở: được chia sẻ lại khi ghi công tác giả, được chỉnh sửa, không dùng cho mục đích thương mại.
Video bài giảng thật từ MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020).
Trần Ngọc Tây
Bài giảng rất rõ ràng, dễ hiểu. Task 9 verification test.
Đăng nhập để đánh giá học liệu này.
Trần Ngọc Tây
Cảm ơn thầy về bài giảng! (Task 9 verification comment)
Trần Ngọc Tây
Fix 3 live verification comment - should appear without reload.
Trần Ngọc Tây
ok hay
Đăng nhập để bình luận.