Understand about Regular Language

In this article we will study concept of Regular Language.

Regular Language

A language is said to be regular if it is accepted by finite automata or have regular expression. In other words we can say if particular language is accepted by machine then the language is said to be regular. A regular language described by regular grammar.

The concept of regular language is easy to understand by the pictorial representation mentioned below. Pictorial representation defines how regular expression, Regular grammar or finite automata defines the regular language.

Regular Language in TOC

A language is a set of strings which are made up of characters from a specified alphabet, or set of symbols. Regular languages are a subset of the set of all strings. Which are used in parsing and designing programming languages.

These are useful for helping to recognize patterns in data and group certain computational problems together. Regular languages plays important role in computability theory. It can model computational problems which require a very small amount of memory. For example, a finite automaton can generate a regular language to describe if a light switch is on or off, but it cannot keep track of how many times the light was switched on or off.

The machine above can know what state it is currently in, on or off, but it doesn't know what the history of flips was to get it to where it is (i.e. it doesn't know how many times the switch has been flipped on or off).

Finite automata generate or model regular languages. This means that regular languages can be described by a simple state machine diagram. A finite state machine, M, describes a given language, L. M is said to accept a string w if the machine starts in a start state, undergoes some series of state transitions, and ends up in an accepting state. We say that the machine M recognizes the language L if M accepts all strings w that are in L. A language is a regular language if there is a finite automaton that recognizes it. (It will be discuss in detail in some other article).

Operations on Regular Languages

A regular language can be represented by a string of symbols and operations.

Concatenation

Concatenation is an operation that combines two symbols, sets, or languages. There are two main ways to write a concatenation.  X∘Y and XY both mean “X concatenated with Y.” Languages can also be concatenated: L₁​∘L₂​ means strings from  L₁​ are written first, and then strings from L₂ come after.

Formally, concatenation is defined as follows:  A∘B={xy∣ x ∈ A and y ∈ B}.

Union

Union is an operation where a finite state machine can make one choice or another at any step (this can also be thought of as an “or” operation). For example, there could be a finite state machine that can choose between concatenating XX with YY or concatenating XX with ZZ. Or is written with a vertical bar, and the expression from the previous sentence looks like this: (X∘Y∣X∘Z).

Formally, union is described as follows: A∪B={x∣x∈A or x∈B}. Note, here the vertical bar means “such that.”

Kleene Star

The Kleene star is an operation denoted by an asterisk * that basically represents repeated self-concatenation. For example, if a language LL represents all strings of the form X*, then this language includes X, XX, XXXXXX, XXXXXXXXXXX, etc. The Kleene star can repeat the symbol it operates on any number of times.

The regular language X∘Y∣Z^∗ represents strings of the form “X concatenated with Y or Z repeated any number of times.”

Formally, the Kleene star is defined as follows: A^∗={x₁​x₂​...x_k​ ∣ k≥0 and each xi​∈A}. The Kleene star is a unary operation since it operates only on one thing instead of two (unlike union and concatenation, which are binary operations).

Because k can be 0,  x can be repeated 0 times. This means that the empty string is always a member of A^∗.

The Empty String

Another important symbol is ϵ which represents the empty string.

Language Notation

Languages are often written as follows: L=(some pattern)∣∣​(some condition), where the vertical bar means "such that." The pattern often resembles something like this 0ⁿ1ⁿ, where the exponent actually represents a unary operation — the 0 would be repeated n times. For example,  0⁴1⁴ is written out as 0000111100001111.

Also, Study about: 

• Mealy Machine
• Moore Machine
• Rice Theorem
• Brief about Turing Machine
• Multi Dimension Turing Machine
• Multiple Turing Machine
• Parikh Theorem in TOC
• Parse Tree or Derivation Tree
• What do you Understand by Derivation
• MyHill Nerode Theorem
• Minimize Myhill Nerode Theorem
• Push Down Automata
• Know Where we use Automata
• What do you understand by Derivation of Grammar
• What is Context-free Grammar
• Example based on CFG
• Regular Expression in TOC
• What is Two-way infinite Turing machine?
• Example to generate Parse tree from the given grammar

Also Read, some interview tips

• Why Should I Hire You?
• What are your weaknesses?
• What are your greatest strengths?
• Tell me about yourself.
• What's the reason behind leaving your current position at your company?
• Do You Know how the power of Keywords impacts on Resume?
• Top 8 Proofreading Tips and Techniques in 2022.
• Top Ten Technical Resume Writing Tips in 2022.
• Tips for your resume before you get entry to Job Market
• What Questions you can ask HR during the Interview.
• How to make an impressive resume?
• Best Resume writing Technique.
• What Questions you can ask HR during the Interview.