Introduction to Formal Languages and Automata Theory

For Complete YouTube Video: Click Here

In this class, We discuss Introduction to Formal Languages and Automata Theory.

As this is our first class, we introduce the concepts we learn in our coming classes.

The first ten classes are essential to understand. The remaining classes depend on the understanding of the first ten classes.

We take an example and understand the introduction.

Take a keyboard; For simplicity, our keyboard is having two keys, 0 and 1.

Assume we have typed the input 100111. The input is saved in RAM.

The below diagram shows the keyboard and RAM.

Suppose we need to write a logic to identify the input strings contain the last character ‘1’.

The logic is very simple. We move on the input string to the last character and check the last character is 1.

We use the terms logic, program, and machine interchangeably.

Think of a situation where a memory device is unavailable, where memory was not invented in the 1960s.

But we have Electronic devices. We call them machines. The machine can process, but memory is not available.

The logic we used above will not be suitable if memory is not available to our device.

The first part of the subject deals with logics that can access strings without memory.

The second part of the subject deals with logics that can be implemented if a stack-based memory device is available.

We have a memory device, but the device can do only stack operations push and pop.

With this memory availability, we can improve your computational capability.

The complete subject deals with the evolution of computations.

The third part of the subject deals with logic with sequential access of the memory device.

We have a memory device. We can move on the memory device one step left or one step right.

We can move sequentially. Not random access to data.

If we need to move from the first location to the tenth location, we have to pass the second location than the third location, and so on.

In the subject, we understand how computational capabilities increased with the evolution of memory access.