Unit - 1

Introduction

Q1) Write about the alphabet, string and language?

A1) Alphabet

●      Definition − An alphabet is any finite set of symbols.

●      Example − ∑ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and ‘d’ are symbols.

Strings

●      Definition − A string is a finite sequence of symbols taken from ∑.

●      Example − ‘cabcad’ is a valid string on the alphabet set ∑ = {a, b, c, d}

Language

●      Definition − A language is a subset of ∑* for some alphabet ∑. It can be finite or infinite.

●      Example − If the language takes all possible strings of length 2 over ∑ = {a, b}, then

L1 = {ab, aa, ba, bb} finite language

L2 = {a,aa,aaa,abb,abab}  infinite language

Q2) Write short notes on automata and grammar?

A2) Automata

●      The term "Automata" is derived from the Greek word "αὐτόματα" which means "self-acting". An automaton (Automata in plural) is an abstract self-propelled computing system that automatically follows a predetermined operation sequence.

●      The primary reason behind the development of the automata theory was the development of methods to explain and analyse the complex behaviour of separate systems.

Grammar

Simplifying Context Free Grammars

A context free grammar (CFG) is in Chomsky Normal Form (CNF) if all production

Rules satisfy one of the following conditions:

A non-terminal generating a terminal (e.g.; X->x)

A non-terminal generating two non-terminals (e.g.; X->YZ)

Start symbol generating ε. (e.g.; S-> ε)

Consider the following grammars,

G1 = {S->a, S->AZ, A->a, Z->z}

G2 = {S->a, S->aZ, Z->a}

The grammar G1 is in CNF as production rules satisfy the rules specified for CNF. However, the grammar G2 is not in CNF as the production rule S->aZ contains terminal followed by non-terminal which does not satisfy the rules specified for CNF.

Q3) How to convert CFG to CNF?

A3) Step 1. Remove start from RHS. If start symbol S is at the RHS of any production in the grammar, create a new production as: S0->S where S0 is the new start symbol.

Step 2. Remove null, unit and useless productions. If CFG comprises of any production rules, remove them.

Step 3. Remove terminals from RHS. For e.g.; production rule X->xY can be decomposed as: X->ZY Z->x

Step 4. Remove RHS with more than two non-terminals. e.g.; production rule X->XYZ can be decomposed as:

X->PZ

P->XY

Q4) Explain deterministic finite automata?

A4) In this, for each input symbol, the state to which the machine will move can be determined. As it has a finite number of states, the machine is called Deterministic Finite Machine or Deterministic Finite Automaton.

An automaton can be represented by a 5-tuple (Q, ∑, δ, q 0, F), where −

●      Q is a finite set of states.

●      ∑ is a finite set of symbols, called the alphabet of the automaton.

●      δ is the transition function.

●      q0 is the initial state from where any input is processed (q 0 ∈ Q).

●      F is a set of final state/states of Q (F ⊆ Q).

Transition function can be defined as:

δ: Q x ∑→Q 

Representation

A DFA can be represented by digraphs called state diagram. In which:

1. The state is represented by vertices.
2. The arc labeled with an input character shows the transitions.
3. The initial state is marked with an arrow.
4. The final state is denoted by a double circle.

Advantages and disadvantages

●      DFAs are used to model a Turing machine.

●      They are used as++ models of computation.

●      The union/intersection of the languages recognized by two given DFAs.

●      The complement of the language recognized by a given DFA.

Example

1. Q = {q0, q1, q2} 
2. ∑ = {0,1} 
3. q0 = {q0} 
4. F = {q2} 

Solution:

Transition Diagram:

Transition Table:

Q5) Describe state transition graph?

A5) A DFA A = (Q, Σ, δ, q0, F ) transition diagram is a graph that looks like this:

a. In Q, there is a node for each state.

b. Let q a p for each state q in Q and each input symbol a in ∑, let δ(q, a) = p.

The transition diagram thus displays a labeled arc from node q to node p. If a number of input symbols induce transitions from q to p, the transition diagram can have a single arc labeled with the list of these symbols.

c. There is a labeled arrow into the initial state q0. Start This arrow does not start at any of the nodes.

d. A double circle denotes nodes that correspond to accepting states in F. There is just one c in states that are not in F.

A transition diagram, also known as a state transition diagram, is a directed graph that looks like this:

●      Each state in Q has a node, which is represented by the circle.

●      If δ(q, a) = p, there is a directed edge from node q to node p designated a.

●      There is an arrow with no source in the initial state.

●      A double circle indicates accepting states or final states.

Example: A string of letters and digits that starts with a letter can be defined as an identifier.

●      Token letter stands for any of the symbols a, . . . , z, A, . . . , Z.

●      The token digit represents 0, 1,..., 9.

The state-transition diagram in Figure defines the set of identifiers.

Fig: State -diagram for specifying identifiers

Q6) Write any example for transition diagram?

A6) The transition diagram for the DFA that we built in Example is shown in Figure. The three nodes that correspond to the three states can be seen in that diagram. The start state q1 is represented by a Start arrow, while the acceptance state q1 is represented by a double circle. Each state has one identified arc 0 and one labeled arc 1 (although the two arcs are combined into one with a double label in the case of q1). Each of the arcs corresponds to one of the facts that have been developed.

Fig: Transition diagram for DFA

Q7) Write about transition table?

A7) A transition table is a tabular representation of a function δ that accepts two inputs and returns a value, such as. The states are represented by the table's rows, while the inputs are represented by the table's columns. The state is the entry for the row that corresponds to state q and the column that corresponds to input δ(q,a).

The transition table is a table that shows how the transition function works. It takes two inputs (a state and a symbol) and outputs a state (the "next state").

The following elements make up a transition table:

●      The input symbols are represented by columns.

●      States are represented by rows.

●      The next state corresponds to the entries.

●      An arrow with no source denotes the initial state.

●      A star indicates the accept state.

Example:  consider the below diagram

Solution: The following is the transition table for the given NFA:

The first row of the transition table reads: When the current state is q0, the next state on input 0 is q0, and the following state on input 1 is q1.

When the current state is q1, the next state will be either q1 or q2, and when the current state is q2, the following state will be q2.

When the current state is q2 on input 0, the following state is q1, and when the current state is q3 on input 1, the next state is q3.

When the current state is q3 on input 0, the following state is q2, and when the current state is q3 on input 1, the next state is q2.

Q8) Explain language of DFA?

A8) We can now define the notion of acceptance of a string, and thus acceptance of a language, in terms of a DFA.

If ˆδ(q0, x) ∈  F, a string x is said to be accepted by a DFA A = (Q, Σ, δ, q0, F). That is, the DFA will achieve a final state if the string x ∈ Σ ∗ is applied in the initial state.

The language accepted by A is defined as the set of all strings accepted by the DFA A and is denoted by L(A ). That is to say,

L(A ) = {x ∈ Σ* | ˆδ(q0, x) ∈ F}

Example: Take into account the following DFA:

The string ab is the only way to get from the beginning state q0 to the final state q2, and abb is the only way to get to another final state q3. As a result, the DFA's approved language is

{ab, abb}.

Example: Let us recollect the DFA's transition diagram, as given below.

1. It’s important to remember that if the input contains aa, the DFA will take us from the starting state p to the final state r. Due to the fact that r is also a trap state, we will remain at r on any future input.

2. If there is no aa in the input, we will shuffle between p and q but never reach the ultimate state r.

As a result, the DFA accepts the set of all strings over a, b that have aa as a substring, i.e.

{xaay | x, y ∈ {a, b}*}.

Q9) Describe non-deterministic finite automata?

A9) In NDFA, the machine can move to any combination of the states. Hence, it is

Called Non-deterministic Automaton.

It has a finite number of states.

●      Q → Finite non-empty set of states.

●      ∑ → Finite non-empty set of input symbols.

●      ∂ → Transitional Function.

●      q0 → Beginning state.

●      F → Final State

Transition function can be defined as:

δ: Q x ∑ →2Q

Graphical Representation of NFA

An NFA can be represented by digraphs called state diagram. In which:

1. The state is represented by vertices.
2. The arc labeled with an input character show the transitions.
3. The initial state is marked with an arrow.
4. The final state is denoted by the double circle.

Example

1. Q = {q0, q1, q2} 
2. ∑ = {0, 1} 
3. q0 = {q0} 
4. F = {q2}

Solution:

Transition Diagram:

Transition table:

In this figure, we can see that the current state is q0 (input 0), and the next state will be q0, q1 (input 1) so the next state is q1. When the current state is q1 (input 0), the next state will be q2 (input 1), the next state is q0. When the current state is q2 (input 0), the next state is q2 (input 1), the next state will be q1 or q2.

Q10) What do you mean by NFA with epsilon transition?

A10) Epsilon closure for a given state X is a set of states which can be reached from the states X with only (null) or ε moves including the state X itself.  In other words, ε - closure for a state can be obtained by union operation of the ε - closure of the states which can be reached from X with a single ε move in recursive manner.

For the above example ∈ closures are as follows:

∈closure(A): {A, B, C}

∈closure(B): {B, C}

∈closure(C): {C}

Deterministic Finite Automata (DFA): DFA is a finite automata where, for all cases,

When a single input is given to a single state, the machine goes to a single state, i.e., all

The moves of the machine can be uniquely determined by the present state and the

Present input symbol.

Steps to Convert NFA with ε-move to DFA:

Step 1: Take ∈ closure for the beginning state of NFA as beginning state of DFA.

Step 2: Find the states that can be traversed from the present for each input symbol

(Union of transition value and their closures for each state of NFA present in current

State of DFA).

Step 3: If any new state is found take it as current state and repeat step 2.

Step 4: Do repeat Step 2 and Step 3 until no new state present in DFA transition table.

Step 5: Mark the states of DFA which contains final state of NFA as final states of DFA.

Transition state table for DFA corresponding to above NFA

DFA State diagram

Q11) Write the equivalence of DFA and NFA?

A11) It would seem superficially that deterministic and non-deterministic finite state automata are totally distinct beasts. However, it turns out that they are equivalent. There is a DFA for every language recognized by an NFA that recognizes that language and vice versa.

The NFA to DFA conversion algorithm is relatively simple, even though the resulting DFA is substantially more complicated than the original NFA. I will illustrate this equivalence after the hop and also go through a brief example of converting an NFA to an equivalent DFA.

DFA and NFA Theorem proof -

Let's formally state the theorem we are proving before continuing:

Theorem:

Let the language L ⊆ Σ* be recognized by NFA N = (Σ, Q, q0, F, δ) and assume L.

A DFA D= (Σ, Q ', q'0, F', δ ') exists that also accepts L. (L(N)= L(D)).

We are able to prove by induction that D is equal to N by allowing each state in the DFA D to represent a set of states in the NFA N. Let's define the parameters of D: before we start proofing,

●      Q’ is equal to the powerset of Q, Q’ = 2Q

●      q’0 = {q0}

●      F’ is the set of states in Q’ that contain any element of F, F’ = {q ∈ Q’|q ∩ F ≠ Ø}

●      δ’ is the transition function for D.  δ’(q,a) = Up∈ q δ(p, a)for q ∈ Q’ and a ∈ Σ

It's worth more explaining, I think δ '. Note that in the set of states Q 'in D, each state is a set of states from Q in N itself. Determine the transition δ (p,a) for each state p in state q in Q 'of D (p is a single state from Q). The union of all δ(q, a) is δ(q,a) .

Now we will demonstrate δ’(q0’, x) =δ’(q0 , x) that for every x  i.e L(D) = L (N)

Q12) How to minimize finite automata?

A12) It is possible to create infinitely many finite state automata for a given regular language L to accept L. The answer is that there will be a loop in the transition diagram centered on a given DFA M1. To have more states and L(M1) = L(M2) = L, we can create a new DFA M2. And we can create a DFA M3 with even more states and L(M3) = L from DFA M2.

For instance, given a DFA M1, we can create a DFA M2 to have more states and

L(M1) = L(M2) = L.

Example: The following two DFA's are identical to M1 and M2. The collection above the alphabet Σ = {0,1} is accepted by {0n | n>0} both machines.

Machine M2 states q1, q2 and q3 are identical, we can combine these three states in one state as qt in machine M1.

The state qg and qh of the M2 machine are identical, these two states can be combined in one state as qf in the M1 machine.

Q13) Write any example of DFA?

A13) FA with ∑ = {0, 1} accepts an even number of 0s and even number of 1s.

Solution:

For inputs 0 and 1, this FA will consider four possible phases. The stages could be:

Here, q0 is both a start and a finish state. It's worth noting that the 0s and 1s are kept in a symmetrical pattern. Each state has its own set of connotations, such as:

q0: a state with an even number of 0's and 1's.

q1: a state in which there are an odd number of 0s and an even number of 1s.

q2: a state with an odd amount of 0's and 1's.

q3: a state in which there are an even number of 0s and an odd number of 1s.

Q14) Explain NFA with any example?

A14) Create an NFA with the value ∑ = {0, 1} and a double '1' followed by a double '0'.

Solution:

The double 1 FA is as follows:

It should be followed by a double 0 immediately.

Then,

Any string of 0 and 1 can now come before double 1. Similarly, any string of 0 and 1 can follow double 0.

As a result, the NFA becomes:

Now take a look at the string 01100011.

q0 → q1 → q2 → q3 → q4 → q4 → q4 → q4 

Q15) Write the difference between DFA and NFA?

A15) Difference between DFA and NFA