<!DOCTYPE html><html><body><title>Automata Theory Tutorial</title>

<h1>Automata Theory Tutorial</h1>

<p><b>Automata Theory</b> is a branch of computer science that deals with designing abstract selfpropelled computing devices that follow a predetermined sequence of operations automatically. An automaton with a finite number of states is called a <b>Finite Automaton</b>. This is a brief and concise tutorial that introduces the fundamental concepts of Finite Automata, Regular Languages, and Pushdown Automata before moving onto Turing machines and Decidability.</p>

<h1>Audience</h1>

<p>This tutorial has been prepared for students pursuing a degree in any information technology or computer science related field. It attempts to help students grasp the essential concepts involved in automata theory.</p>

<h1>Prerequisites</h1>

<p>This tutorial has a good balance between theory and mathematical rigor. The readers are expected to have a basic understanding of discrete mathematical structures.</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Automata Theory Introduction</title>

<h1>Automata Theory Introduction</h1>

<h2>Automata – What is it?</h2>

<p>The term "Automata" is derived from the Greek word "αὐτόματα" which means "self-acting". An automaton (Automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically.</p>

<p>An automaton with a finite number of states is called a <b>Finite Automaton</b> (FA) or <b>Finite State Machine</b> (FSM).</p>

<h3>Formal definition of a Finite Automaton</h3>

<p>An automaton can be represented by a 5-tuple (Q, &sum;, &delta;, q₀, F), where &minus;</p>

<p><b>Q</b> is a finite set of states.</p>

<p><b>&sum;</b> is a finite set of symbols, called the <b>alphabet</b> of the automaton.</p>

<p><b>&delta;</b> is the transition function.</p>

<p><b>q₀</b> is the initial state from where any input is processed (q₀ &isin; Q).</p>

<p><b>F</b> is a set of final state/states of Q (F &sube; Q).</p>

<h2>Related Terminologies </h2>

<h3>Alphabet</h3>

<p><b>Definition</b> &minus; An <b>alphabet</b> is any finite set of symbols.</p>

<p><b>Example</b> &minus; &sum; = {a, b, c, d} is an <b>alphabet set</b> where ‘a’, ‘b’, ‘c’, and ‘d’ are <b>symbols</b>.</p>

<h3>String</h3>

<p><b>Definition</b> &minus; A <b>string</b> is a finite sequence of symbols taken from &sum;.</p>

<p><b>Example</b> &minus; ‘cabcad’ is a valid string on the alphabet set &sum; = {a, b, c, d}</p>

<h3>Length of a String</h3>

<p><b>Definition</b> &minus; It is the number of symbols present in a string. (Denoted by <b>|S|</b>).</p>

<p><b>Examples</b> &minus;</p>

<p>If S = ‘cabcad’, |S|= 6</p>

<p>If |S|= 0, it is called an <b>empty string</b> (Denoted by <b>&lambda;</b> or <b>&epsilon;</b>)</p>

<h3>Kleene Star</h3>

<p><b>Definition</b> &minus; The Kleene star, <b>&sum;*</b>, is a unary operator on a set of symbols or strings, <b>&sum;</b>, that gives the infinite set of all possible strings of all possible lengths over <b>&sum;</b> including <b>&lambda;</b>.</p>

<p><b>Representation</b> &minus; &sum;* = &sum;₀ &cup; &sum;₁ &cup; &sum;₂ &cup;……. where &sum;_p is the set of all possible strings of length p.</p>

<p><b>Example</b> &minus; If &sum; = {a, b}, &sum;* = {&lambda;, a, b, aa, ab, ba, bb,………..}</p>

<h3>Kleene Closure / Plus</h3>

<p><b>Definition</b> &minus; The set <b>&sum;⁺</b> is the infinite set of all possible strings of all possible lengths over &sum; excluding &lambda;.</p>

<p><b>Representation</b> &minus; &sum;⁺ = &sum;₁ &cup; &sum;₂ &cup; &sum;₃ &cup;…….</p>

<p><b>Example</b> &minus; If &sum; = { a, b } , &sum;⁺ = { a, b, aa, ab, ba, bb,………..}</p>

<h3>Language</h3>

<p><b>Definition</b> &minus; A language is a subset of &sum;* for some alphabet &sum;. It can be finite or infinite.</p>

<p><b>Example</b> &minus; If the language takes all possible strings of length 2 over &sum; = {a, b}, then L = { ab, bb, ba, bb}</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Deterministic Finite Automaton</title>

<h1>Deterministic Finite Automaton</h1>

<p>Finite Automaton can be classified into two types &minus;</p>

<h2>Deterministic Finite Automaton (DFA)</h2>

<p>In DFA, for each input symbol, one can determine the state to which the machine will move. Hence, it is called <b>Deterministic Automaton</b>. As it has a finite number of states, the machine is called <b>Deterministic Finite Machine</b> or <b>Deterministic Finite Automaton.</b></p>

<h2>Formal Definition of a DFA</h2>

<p>A DFA can be represented by a 5-tuple (Q, &sum;, &delta;, q₀, F) where &minus;</p>

<p><b>Q</b> is a finite set of states.</p>

<p><b>&sum;</b> is a finite set of symbols called the alphabet.</p>

<p><b>&delta;</b> is the transition function where &delta;: Q &times; &sum; &rarr; Q </p>

<p><b>q₀</b> is the initial state from where any input is processed (q₀ &isin; Q).</p>

<p><b>F</b> is a set of final state/states of Q (F &sube; Q).</p>

<h2>Graphical Representation of a DFA</h2>

<p>A DFA is represented by digraphs called <b>state diagram</b>.</b></p>

<h3>Example</h3>

<p>Let a deterministic finite automaton be &rarr;</p>

<p>Transition function &delta; as shown by the following table &minus;</p>

<p>Its graphical representation would be as follows &minus;</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Non-deterministic Finite Automaton</title>

<h1>Non-deterministic Finite Automaton</h1>

<p>In NDFA, for a particular input symbol, the machine can move to any combination of the states in the machine. In other words, the exact state to which the machine moves cannot be determined. Hence, it is called <b>Non-deterministic Automaton</b>. As it has finite number of states, the machine is called <b>Non-deterministic Finite Machine</b> or <b>Non-deterministic Finite Automaton</b>.</p>

<h3>Formal Definition of an NDFA</h3>

<p>An NDFA can be represented by a 5-tuple (Q, &sum;, &delta;, q₀, F) where &minus;</p>

<p><b>Q</b> is a finite set of states.</p>

<p><b>&sum;</b> is a finite set of symbols called the alphabets.</p>

<p><b>&delta;</b> is the transition function where &delta;: Q &times; &sum; &rarr; 2^Q</p>

<p>(Here the power set of Q (2^Q) has been taken because in case of NDFA, from a state, transition can occur to any combination of Q states)</p>

<p><b>q₀</b> is the initial state from where any input is processed (q₀ &isin; Q).</p>

<p><b>F</b> is a set of final state/states of Q (F &sube; Q).</p>

<h3>Graphical Representation of an NDFA: (same as DFA)</h3>

<p>An NDFA is represented by digraphs called state diagram.</p>

<p><b>Example</b></p>

<p>Let a non-deterministic finite automaton be &rarr;</p>

<p>The transition function &delta; as shown below &minus;</p>

<p>Its graphical representation would be as follows &minus;</p>

<h2>DFA vs NDFA</h2>

<p>The following table lists the differences between DFA and NDFA.</p>

<h2>Acceptors, Classifiers, and Transducers</h2>

<h3>Acceptor (Recognizer)</h3>

<p>An automaton that computes a Boolean function is called an <b>acceptor</b>. All the states of an acceptor is either accepting or rejecting the inputs given to it.</p>

<h3>Classifier</h3>

<p>A <b>classifier</b> has more than two final states and it gives a single output when it terminates.</p>

<h3>Transducer</h3>

<p>An automaton that produces outputs based on current input and/or previous state is called a <b>transducer</b>. Transducers can be of two types &minus;</p>

<p><b>Mealy Machine</b> &minus; The output depends both on the current state and the current input.</p>

<p><b>Moore Machine</b> &minus; The output depends only on the current state.</p>

<h2>Acceptability by DFA and NDFA</h2>

<p>A string is accepted by a DFA/NDFA iff the DFA/NDFA starting at the initial state ends in an accepting state (any of the final states) after reading the string wholly.</p>

<p>A string S is accepted by a DFA/NDFA (Q, &sum;, &delta;, q₀, F), iff</p>

<p>The language <b>L</b> accepted by DFA/NDFA is</p>

<p>A string S′ is not accepted by a DFA/NDFA (Q, &sum;, &delta;, q₀, F), iff</p>

<p>The language L′ not accepted by DFA/NDFA (Complement of accepted language L) is</p>

<p><b>Example</b></p>

<p>Let us consider the DFA shown in Figure 1.3. From the DFA, the acceptable strings can be derived.</p>

<p>Strings accepted by the above DFA: {0, 00, 11, 010, 101, ...........}</p>

<p>Strings not accepted by the above DFA: {1, 011, 111, ........}</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>NDFA to DFA Conversion</title>

<h1>NDFA to DFA Conversion</h1>

<h2>Problem Statement</h2>

<p>Let <b>X = (Q_x, &sum;, &delta;_x, q₀, F_x)</b> be an NDFA which accepts the language L(X). We have to design an equivalent DFA <b>Y = (Q_y, &sum;, &delta;_y, q₀, F_y)</b> such that <b>L(Y) = L(X)</b>. The following procedure converts the NDFA to its equivalent DFA &minus;</p>

<h2>Algorithm</h2>

<p><b>Input</b> &minus; An NDFA</p>

<p><b>Output</b> &minus; An equivalent DFA</p>

<p><b>Step 1</b> &minus; Create state table from the given NDFA.</p>

<p><b>Step 2</b> &minus; Create a blank state table under possible input alphabets for the equivalent DFA.</p>

<p><b>Step 3</b> &minus; Mark the start state of the DFA by q0 (Same as the NDFA).</p>

<p><b>Step 4</b> &minus; Find out the combination of States {Q₀, Q₁,... , Q_n} for each possible input alphabet.</p>

<p><b>Step 5</b> &minus; Each time we generate a new DFA state under the input alphabet columns, we have to apply step 4 again, otherwise go to step 6.</p>

<p><b>Step 6</b> &minus; The states which contain any of the final states of the NDFA are the final states of the equivalent DFA.</p>

<h2>Example</h2>

<p>Let us consider the NDFA shown in the figure below.</p>

<p>Using the above algorithm, we find its equivalent DFA. The state table of the DFA is shown in below.</p>

<p>The state diagram of the DFA is as follows &minus;</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>DFA Minimization</title>

<h1>DFA Minimization</h1>

<h2>DFA Minimization using Myphill-Nerode Theorem</h2>

<h3>Algorithm</h3>

<p><b>Input</b> &minus; DFA</p>

<p><b>Output</b> &minus; Minimized DFA</p>

<p><b>Step 1</b> &minus; Draw a table for all pairs of states (Q_i, Q_j) not necessarily connected directly [All are unmarked initially]</p>

<p><b>Step 2</b> &minus; Consider every state pair (Q_i, Q_j) in the DFA where Q_i &isin; F and Q_j &notin; F or vice versa and mark them. [Here F is the set of final states]</p>

<p><b>Step 3</b> &minus; Repeat this step until we cannot mark anymore states &minus;</p>

<p>If there is an unmarked pair (Q_i, Q_j), mark it if the pair {&delta; (Q_i, A), &delta; (Q_i, A)} is marked for some input alphabet.</p>

<p><b>Step 4</b> &minus; Combine all the unmarked pair (Q_i, Q_j) and make them a single state in the reduced DFA.</p>

<h3>Example</h3>

<p>Let us use Algorithm 2 to minimize the DFA shown below.</p>

<p><b>Step 1</b> &minus; We draw a table for all pair of states.</p>

<p><b>Step 2</b> &minus; We mark the state pairs.</p>

<p><b>Step 3</b> &minus; We will try to mark the state pairs, with green colored check mark, transitively. If we input 1 to state ‘a’ and ‘f’, it will go to state ‘c’ and ‘f’ respectively. (c, f) is already marked, hence we will mark pair (a, f). Now, we input 1 to state ‘b’ and ‘f’; it will go to state ‘d’ and ‘f’ respectively. (d, f) is already marked, hence we will mark pair (b, f).</p>

<p>After step 3, we have got state combinations {a, b} {c, d} {c, e} {d, e} that are unmarked.</p>

<p>We can recombine {c, d} {c, e} {d, e} into {c, d, e}</p>

<p>Hence we got two combined states as &minus; {a, b} and {c, d, e}</p>

<p>So the final minimized DFA will contain three states {f}, {a, b} and {c, d, e}</p>

<h2>DFA Minimization using Equivalence Theorem</h2>

<p>If X and Y are two states in a DFA, we can combine these two states into {X, Y} if they are not distinguishable. Two states are distinguishable, if there is at least one string S, such that one of &delta; (X, S) and &delta; (Y, S) is accepting and another is not accepting. Hence, a DFA is minimal if and only if all the states are distinguishable.</p>

<h3>Algorithm 3</h3>

<p><b>Step 1</b> &minus; All the states <b>Q</b> are divided in two partitions &minus; <b>final states</b> and <b>non-final states</b> and are denoted by <b>P₀</b>. All the states in a partition are 0^th equivalent. Take a counter <b>k</b> and initialize it with 0.</p>

<p><b>Step 2</b> &minus; Increment k by 1. For each partition in P_k, divide the states in P_k into two partitions if they are k-distinguishable. Two states within this partition X and Y are k-distinguishable if there is an input <b>S</b> such that <b>&delta;(X, S)</b> and <b>&delta;(Y, S)</b> are (k-1)-distinguishable.</p>

<p><b>Step 3</b> &minus; If P_k &ne; P_k-1, repeat Step 2, otherwise go to Step 4.</p>

<p><b>Step 4</b> &minus; Combine k^th equivalent sets and make them the new states of the reduced DFA.</p>

<h3>Example</h3>

<p>Let us consider the following DFA &minus;</p>

<p>Let us apply the above algorithm to the above DFA &minus;</p>

<p>Hence, P₁ = P₂.</p>

<p>There are three states in the reduced DFA. The reduced DFA is as follows &minus;</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Moore and Mealy Machines</title>

<h1>Moore and Mealy Machines</h1>

<p>Finite automata may have outputs corresponding to each transition. There are two types of finite state machines that generate output &minus;</p>

<h3>Mealy Machine</h3>

<p>A Mealy Machine is an FSM whose output depends on the present state as well as the present input.</p>

<p>It can be described by a 6 tuple (Q, &sum;, O, &delta;, X, q₀) where &minus;</p>

<p><b>Q</b> is a finite set of states.</p>

<p><b>&sum;</b> is a finite set of symbols called the input alphabet.</p>

<p><b>O</b> is a finite set of symbols called the output alphabet.</p>

<p><b>&delta;</b> is the input transition function where &delta;: Q &times; &sum; &rarr; Q</p>

<p><b>X</b> is the output transition function where X: Q &times; &sum; &rarr; O</p>

<p><b>q₀</b> is the initial state from where any input is processed (q₀ &isin; Q).</p>

<p>The state table of a Mealy Machine is shown below &minus;</p>

<p>The state diagram of the above Mealy Machine is &minus;</p>

<h3>Moore Machine</h3>

<p>Moore machine is an FSM whose outputs depend on only the present state.</p>

<p>A Moore machine can be described by a 6 tuple (Q, &sum;, O, &delta;, X, q₀) where &minus;</p>

<p><b>Q</b> is a finite set of states.</p>

<p><b>&sum;</b> is a finite set of symbols called the input alphabet.</p>

<p><b>O</b> is a finite set of symbols called the output alphabet.</p>

<p><b>&delta;</b> is the input transition function where &delta;: Q &times; &sum; &rarr; Q</p>

<p><b>X</b> is the output transition function where X: Q &rarr; O</p>

<p><b>q₀</b> is the initial state from where any input is processed (q₀ &isin; Q).</p>

<p>The state table of a Moore Machine is shown below &minus;</p>

<p>The state diagram of the above Moore Machine is &minus;</p>

<h3>Mealy Machine vs. Moore Machine</h3>

<p>The following table highlights the points that differentiate a Mealy Machine from a Moore Machine.</p>

<h2>Moore Machine to Mealy Machine</h2>

<h3>Algorithm 4</h3>

<p><b>Input</b> &minus; Moore Machine</p>

<p><b>Output</b> &minus; Mealy Machine</p>

<p><b>Step 1</b> &minus; Take a blank Mealy Machine transition table format.</p>

<p><b>Step 2</b> &minus; Copy all the Moore Machine transition states into this table format.</p>

<p><b>Step 3</b> &minus; Check the present states and their corresponding outputs in the Moore Machine state table; if for a state Q_i output is m, copy it into the output columns of the Mealy Machine state table wherever Q_i appears in the next state.</p>

<h3>Example</h3>

<p>Let us consider the following Moore machine &minus;</p>

<p>Now we apply Algorithm 4 to convert it to Mealy Machine.</p>

<p><b>Step 1 &amp; 2</b> &minus;</p>

<p><b>Step 3</b> &minus;</p>

<h2>Mealy Machine to Moore Machine</h2>

<h3>Algorithm 5</h3>

<p><b>Input</b> &minus; Mealy Machine</p>

<p><b>Output</b> &minus; Moore Machine</p>

<p><b>Step 1</b> &minus; Calculate the number of different outputs for each state (Q_i) that are available in the state table of the Mealy machine.</p>

<p><b>Step 2</b> &minus; If all the outputs of Qi are same, copy state Q_i. If it has n distinct outputs, break Q_i into n states as Q_in where <b>n</b> = 0, 1, 2.......</p>

<p><b>Step 3</b> &minus; If the output of the initial state is 1, insert a new initial state at the beginning which gives 0 output.</p>

<h3>Example</h3>

<p>Let us consider the following Mealy Machine &minus;</p>

<p>Here, states ‘a’ and ‘d’ give only 1 and 0 outputs respectively, so we retain states ‘a’ and ‘d’. But states ‘b’ and ‘c’ produce different outputs (1 and 0). So, we divide <b>b</b> into <b>b₀, b₁</b> and <b>c</b> into <b>c₀, c₁</b>.</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Introduction to Grammars</title>

<h1>Introduction to Grammars</h1>

<p>n the literary sense of the term, grammars denote syntactical rules for conversation in natural languages. Linguistics have attempted to define grammars since the inception of natural languages like English, Sanskrit, Mandarin, etc.</p>

<p>The theory of formal languages finds its applicability extensively in the fields of Computer Science. <b>Noam Chomsky</b> gave a mathematical model of grammar in 1956 which is effective for writing computer languages.</p>

<h2>Grammar</h2>

<p>A grammar <b>G</b> can be formally written as a 4-tuple (N, T, S, P) where &minus;</p>

<p><b>N</b> or <b>V_{<i><small>N</small></i>}</b> is a set of variables or non-terminal symbols.</p>

<p><b>T</b> or <b>&sum;</b> is a set of Terminal symbols.</p>

<p><b>S</b> is a special variable called the Start symbol, S &isin; N</p>

<p><b>P</b> is Production rules for Terminals and Non-terminals. A production rule has the form &alpha; &rarr; &beta;, where &alpha; and &beta; are strings on V_{<i><small>N</small></i>} &cup; &sum; and least one symbol of &alpha; belongs to V_N.</p>

<h3>Example</h3>

<p>Grammar G1 &minus;</p>

<p>Here,</p>

<p><b>S, A,</b> and <b>B</b> are Non-terminal symbols;</p>

<p><b>a</b> and <b>b</b> are Terminal symbols</p>

<p><b>S</b> is the Start symbol, S &isin; N</p>

<p>Productions, <b>P : S &rarr; AB, A &rarr; a, B &rarr; b</b></p>

<h3>Example</h3>

<p>Grammar G2 &minus;</p>

<p>Here,</p>

<p><b>S</b> and <b>A</b> are Non-terminal symbols.</p>

<p><b>a</b> and <b>b</b> are Terminal symbols.</p>

<p><b>&epsilon;</b> is an empty string.</p>

<p><b>S</b> is the Start symbol, S &isin; N</p>

<p>Production <b>P : S &rarr; aAb, aA &rarr; aaAb, A &rarr; &epsilon;</b></p>

<h2>Derivations from a Grammar</h2>

<p>Strings may be derived from other strings using the productions in a grammar. If a grammar <b>G</b> has a production <b>&alpha; &rarr; &beta;</b>, we can say that <b>x &alpha; y</b> derives <b>x &beta; y</b> in <b>G</b>. This derivation is written as &minus;</p>

<h3>Example</h3>

<p>Let us consider the grammar &minus;</p>

<p>Some of the strings that can be derived are &minus;</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Language Generated by a Grammar</title>

<h1>Language Generated by a Grammar</h1>

<p>The set of all strings that can be derived from a grammar is said to be the language generated from that grammar. A language generated by a grammar <b>G</b> is a subset formally defined by</p>

<p>If <b>L(G1) = L(G2)</b>, the Grammar <b>G1</b> is equivalent to the Grammar <b>G2</b>.</p>

<h3>Example</h3>

<p>If there is a grammar</p>

<p>Here <b>S</b> produces <b>AB</b>, and we can replace <b>A</b> by <b>a</b>, and <b>B</b> by <b>b</b>. Here, the only accepted string is <b>ab</b>, i.e.,</p>

<h3>Example</h3>

<p>Suppose we have the following grammar &minus;</p>

<p>The language generated by this grammar &minus;</p>

<h2>Construction of a Grammar Generating a Language</h2>

<p>We’ll consider some languages and convert it into a grammar G which produces those languages.</p>

<h3>Example</h3>

<p><b><i>Problem</i></b> &minus; Suppose, L (G) = {a^m bⁿ | m &ge; 0 and n &gt; 0}. We have to find out the grammar <b>G</b> which produces <b>L(G)</b>.</p>

<p><b><i>Solution</i></b></p>

<p>Since L(G) = {a^m bⁿ | m &ge; 0 and n &gt; 0}</p>

<p>the set of strings accepted can be rewritten as &minus;</p>

<p>Here, the start symbol has to take at least one ‘b’ preceded by any number of ‘a’ including null.</p>

<p>To accept the string set {b, ab, bb, aab, abb, …….}, we have taken the productions &minus;</p>

<p>Thus, we can prove every single string in L(G) is accepted by the language generated by the production set.</p>

<p>Hence the grammar &minus;</p>

<h3>Example</h3>

<p><b><i>Problem</i></b> &minus; Suppose, L (G) = {a^m bⁿ | m &gt; 0 and n &ge; 0}. We have to find out the grammar G which produces L(G).</p>

<p><b><i>Solution</i></b> &minus;</p>

<p>Since L(G) = {a^m bⁿ | m &gt; 0 and n &ge; 0}, the set of strings accepted can be rewritten as &minus;</p>

<p>Here, the start symbol has to take at least one ‘a’ followed by any number of ‘b’ including null.</p>

<p>To accept the string set {a, aa, ab, aaa, aab, abb, …….}, we have taken the productions &minus;</p>

<p>Thus, we can prove every single string in L(G) is accepted by the language generated by the production set.</p>

<p>Hence the grammar &minus;</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Chomsky Classification of Grammars</title>

<h1>Chomsky Classification of Grammars</h1>

<p>According to Noam Chomosky, there are four types of grammars &minus; Type 0, Type 1, Type 2, and Type 3. The following table shows how they differ from each other &minus;</p>

<p>Take a look at the following illustration. It shows the scope of each type of grammar &minus;</p>

<h2>Type - 3 Grammar</h2>

<p><b>Type-3 grammars</b> generate regular languages. Type-3 grammars must have a single non-terminal on the left-hand side and a right-hand side consisting of a single terminal or single terminal followed by a single non-terminal.</p>

<p>The productions must be in the form <b>X &rarr; a or X &rarr; aY</b></p>

<p>where <span style="padding-left:2%;"><b>X, Y &isin; N</b> (Non terminal)</span></p>

<p>and <span style="padding-left:2%;"><b>a &isin; T</b> (Terminal)</span></p>

<p>The rule <b>S &rarr; &epsilon;</b> is allowed if <b>S</b> does not appear on the right side of any rule.</p>

<h3>Example</h3>

<h2>Type - 2 Grammar</h2>

<p><b>Type-2 grammars</b> generate context-free languages.</p>

<p>The productions must be in the form <b>A &rarr; γ</b></p>

<p>where <span style="padding-left:2%;"><b> A &isin; N</b> (Non terminal)</span></p>

<p>and <span style="padding-left:2%;"><b>γ &isin; (T &cup; N)*</b> (String of terminals and non-terminals).</span></p>

<p>These languages generated by these grammars are be recognized by a non-deterministic pushdown automaton.</p>

<h3>Example</h3>

<h2>Type - 1 Grammar</h2>

<p><b>Type-1 grammars</b> generate context-sensitive languages. The productions must be in the form</p>

<p>where <span style="padding-left:2%;"><b>A &isin; N</b> (Non-terminal)</span></p>

<p>and <span style="padding-left:2%;"><b>&alpha;, &beta;, γ &isin; (T &cup; N)*</b> (Strings of terminals and non-terminals)</span></p>

<p>The strings <b>&alpha;</b> and <b>&beta;</b> may be empty, but <b>γ</b> must be non-empty.</p>

<p>The rule <b>S &rarr; &epsilon;</b> is allowed if S does not appear on the right side of any rule. The languages generated by these grammars are recognized by a linear bounded automaton.</p>

<h3>Example</h3>

<h2>Type - 0 Grammar</h2>

<p><b>Type-0 grammars</b> generate recursively enumerable languages. The productions have no restrictions. They are any phase structure grammar including all formal grammars.</p>

<p>They generate the languages that are recognized by a Turing machine.</p>

<p>The productions can be in the form of <b>&alpha; &rarr; &beta;</b> where <b>&alpha;</b> is a string of terminals and nonterminals with at least one non-terminal and <b>&alpha;</b> cannot be null. <b>&beta;</b> is a string of terminals and non-terminals.</p>

<h3>Example</h3>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<pre class="result notranslate">

X &rarr; &epsilon;

X &rarr; a | aY

Y &rarr; b

<h2>Type - 2 Grammar</h2>

<p><b>Type-2 grammars</b> generate context-free languages.</p>

<p>The productions must be in the form <b>A &rarr; γ</b></p>

<p>where <span style="padding-left:2%;"><b> A &isin; N</b> (Non terminal)</span></p>

<p>and <span style="padding-left:2%;"><b>γ &isin; (T &cup; N)*</b> (String of terminals and non-terminals).</span></p>

<p>These languages generated by these grammars are be recognized by a non-deterministic pushdown automaton.</p>

<h3>Example</h3>

<pre class="result notranslate">

S &rarr; X a

X &rarr; a

X &rarr; aX

X &rarr; abc

X &rarr; &epsilon;

<h2>Type - 1 Grammar</h2>

<p><b>Type-1 grammars</b> generate context-sensitive languages. The productions must be in the form</p>

<p style="padding-left:12%;"><b>&alpha; A &beta; &rarr; &alpha; γ &beta;</b></p>

<p>where <span style="padding-left:2%;"><b>A &isin; N</b> (Non-terminal)</span></p>

<p>and <span style="padding-left:2%;"><b>&alpha;, &beta;, γ &isin; (T &cup; N)*</b> (Strings of terminals and non-terminals)</span></p>

<p>The strings <b>&alpha;</b> and <b>&beta;</b> may be empty, but <b>γ</b> must be non-empty.</p>

<p>The rule <b>S &rarr; &epsilon;</b> is allowed if S does not appear on the right side of any rule. The languages generated by these grammars are recognized by a linear bounded automaton.</p>

<h3>Example</h3>

<pre class="result notranslate">

AB &rarr; AbBc

A &rarr; bcA

B &rarr; b

<h2>Type - 0 Grammar</h2>

<p><b>Type-0 grammars</b> generate recursively enumerable languages. The productions have no restrictions. They are any phase structure grammar including all formal grammars.</p>

<p>They generate the languages that are recognized by a Turing machine.</p>

<p>The productions can be in the form of <b>&alpha; &rarr; &beta;</b> where <b>&alpha;</b> is a string of terminals and nonterminals with at least one non-terminal and <b>&alpha;</b> cannot be null. <b>&beta;</b> is a string of terminals and non-terminals.</p>

<h3>Example</h3>

<pre class="result notranslate">

S &rarr; ACaB

Bc &rarr; acB

CB &rarr; DB

aD &rarr; Db

<title>Regular Expressions</title>

<h1>Regular Expressions</h1>

<p>A <b>Regular Expression</b> can be recursively defined as follows &minus;</p>

<p><b>&epsilon;</b> is a Regular Expression indicates the language containing an empty string. <b>(L (&epsilon;) = {&epsilon;})</b></p>

<p><b>&phi;</b> is a Regular Expression denoting an empty language. <b>(L (&phi;) = { })</b></p>

<p><b>x</b> is a Regular Expression where <b>L = {x}</b></p>

<p>If <b>X</b> is a Regular Expression denoting the language <b>L(X)</b> and <b>Y</b> is a Regular Expression denoting the language <b>L(Y)</b>, then</p>

<p><b>X + Y</b> is a Regular Expression corresponding to the language <b>L(X) &cup; L(Y)</b> where <b>L(X+Y) = L(X) &cup; L(Y)</b>.</p>

<p><b>X . Y</b> is a Regular Expression corresponding to the language <b>L(X) . L(Y)</b> where <b>L(X.Y) = L(X) . L(Y)</b></p>

<p><b>R*</b> is a Regular Expression corresponding to the language <b>L(R*)</b>where <b>L(R*) = (L(R))*</b></p>

<p>If we apply any of the rules several times from 1 to 5, they are Regular Expressions.</p>

<h2>Some RE Examples</h2>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Regular Sets</title>

<h1>Regular Sets</h1>

<p>Any set that represents the value of the Regular Expression is called a <b>Regular Set.</b></p>

<h3>Properties of Regular Sets</h3>

<p><b>Property 1</b>. <i>The union of two regular set is regular.</i></p>

<p><b>Proof</b> &minus;</p>

<p>Let us take two regular expressions</p>

<p>So, <span style="padding-left:2%">L₁ = {a, aaa, aaaaa,.....} (Strings of odd length excluding Null)</span></p>

<p>and <span style="padding-left:2%">L₂ ={ &epsilon;, aa, aaaa, aaaaaa,.......} (Strings of even length including Null)</span></p>

<p><b>Hence, proved.</b></p>

<p><b>Property 2.</b> <i>The intersection of two regular set is regular.</i></p>

<p><b>Proof</b> &minus;</p>

<p>Let us take two regular expressions</p>

<p>So, <span style="padding-left:2%">L₁ = { a,aa, aaa, aaaa, ....} (Strings of all possible lengths excluding Null)</span></p>

<p><b>Hence, proved.</b></p>

<p><b>Property 3.</b> <i>The complement of a regular set is regular.</i></p>

<p><b>Proof</b> &minus;</p>

<p>Let us take a regular expression &minus;</p>

<p>So, <span style="padding-left:2%;">L = {&epsilon;, aa, aaaa, aaaaaa, .......} (Strings of even length including Null)</span></p>

<p>Complement of <b>L</b> is all the strings that is not in <b>L</b>.</p>

<p>So, <span style="padding-left:2%;">L’ = {a, aaa, aaaaa, .....} (Strings of odd length excluding Null)</span></p>

<p><b>Hence, proved.</b></p>

<p><b>Property 4.</b> <i>The difference of two regular set is regular.</i></p>

<p><b>Proof</b> &minus;</p>

<p>Let us take two regular expressions &minus;</p>

<p>So, <span style="padding-left:2%;">L₁ = {a, aa, aaa, aaaa, ....} (Strings of all possible lengths excluding Null)</span></p>

<p><b>Hence, proved.</b></p>

<p><b>Property 5.</b> <i>The reversal of a regular set is regular.</i></p>

<p><b>Proof</b> &minus;</p>

<p>We have to prove <b>L^R</b> is also regular if <b>L</b> is a regular set.</p>

<p>Let, <span style="padding-left:2%">L = {01, 10, 11, 10}</span></p>

<p><b>Hence, proved.</b></p>

<p><b>Property 6.</b> <i>The closure of a regular set is regular.</i></p>

<p><b>Proof</b> &minus;</p>

<p>i.e.,<span style="padding-left:2%;"> RE (L) = a (aa)*</span></p>

<p>RE (L*) = a (a)*</p>

<p><b>Hence, proved.</b></p>

<p><b>Property 7.</b> <i>The concatenation of two regular sets is regular.</i></p>

<p><b>Proof &minus;</b></p>

<p>Let <span style="padding-left:4%">RE₁ = (0+1)*0 and RE₂ = 01(0+1)*</span></p>