21ODMCT614-Discrete Mathematical Structure

Boolean Algebra 193 (d) Determine the minterm normal of the Boolean function found in the answer to part a or given in part b; they are equivalent. (e) Discuss the relative simplicity and advantages of the circuit gate diagrams found in answer to parts c and d. 2. Write the circuit (gate) diagram of: (a) f Hx1, x2, x3L = Hx1 • x2 + x3L • Hx2 + x3L + x3. (b) Simplify the function in part a by using basic Boolean algebra laws. (c) Write the circuit (gate) diagram of the result obtained in part b. (d) Draw the on-off switch diagrams of parts a and b. 3. Give a phrase structure grammar to generates the set {0n 1n/n = 0, 1, 2}. 4. Find a phrase structure grammar to generates the set {0m 1n/m and n are non-negative integers}. 5. Let L – {a2, ab} and M = {a, ab, b2} be language over A = {a, b}. Find. (a) LM (b) ML B. Multiple Choice/Objective Type Questions 1. If the switch is on it is represent by: (a) 0 (b) 1 (c) OR (d) NOT 2. If the switch is off it is represented by: (a) 0 (b) 1 (c) OR (d) NOT x X 3. Symbol is used for: (a) NOT gate (13) NOR (c) OR (d) NAND CU IDOL SELF LEARNING MATERIAL (SLM)

194 Discrete Mathematical Structures 4. An AND gate performs logical multiplication on: (a) Inputs (b) Outputs (c) OR gates (d) NOR gates 5. X + XZ is equal to: (a) Z (b) 1 (c) X + Z (d) X Answers 1. (b), 2. (b), 3. (a), 4. (a), 5. (d) 10.9 References References Book: 1. https://www.studocu.com/en/document/university-of-south-asia-pakistan/discrete- mathematics/lecture-notes/chapter-12-boolean-algebra/4292075/view Web Resources: 1. http://web.csulb.edu/~hill/ee201/Boolean%20Algebra 2. http://www.cs.utsa.edu/~bylander/cs2233/languageshandout 3. https://www.javatpoint.com/discrete-mathematics-logic-gates-and-circuits 4. https://www.geeksforgeeks.org/regular-expressions-regular-grammar-and-regular- languages/ CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 11 STATE MACHINE Structure: 11.0 Learning Objectives 11.1 Introduction 11.2 Languages and Grammars 11.3 Phrase Structure Grammars 11.4 Regular Expression and Regular Language 11.4.1 Regular Expression 11.4.2 Regular Languages 11.5 Finite-State Automata 11.6 Finite-State Machine 11.7 Summary of the Unit 11.8 Key Words/Abbreviations 11.9 Learning Activity 11.10 Unit End Questions (MCQ and Descriptive) 11.11 References

196 Discrete Mathematical Structures 11.0 Learning Objectives After studying this unit, you will be able to:
Define State Machine.
Explain Recognition in Regular Languages. 11.1 Introduction
A Finite-State Machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some external inputs and/or a condition is satisfied; the change from one state to another is called a transition.
An FSM is defined by a list of its states, its initial state, and the conditions for each transition. Finite state machines are of two types – deterministic finite state machines and nondeterministic finite state machines. A deterministic finite-state machine can be constructed equivalent to any nondeterministic one.
The finite-state machine has less computational power than some other models of computation such as the Turing machine.
The computational power distinction means there are computational tasks that a Turing machine can do but a FSM cannot. This is because a FSM’s memory is limited by the number of states it has. FSMs are studied in the more general field of automata theory. 11.2 Languages and Grammars Words in the English language can be combined in various ways. The grammar of English tells us whether a combination of words is a valid sentence. For instance, the frog writes neatly is a valid sentence, because it is formed from a noun phrase, the frog, made-up of the verb writes and the adverb neatly. We do not care that this is a nonsensical statement, because we are concerned only with the syntax or form of the sentence, and not it’s semantics or meaning we also CU IDOL SELF LEARNING MATERIAL (SLM)

State Machine 197 note that the combination of words swims quickly mathematics is not a valid sentence because, it does not follow the rules of English grammar. The syntax of a natural language, that is, a spoken language, such as English, French, German or Spanish, is extremely complicated. In fact, it does not seem possible to specify all the rules of syntax for a natural language. Research in the automatic translation of one language to another has led to the concept of a formal language, which, unlike a natural language, is specified by a well-defined set of rules of syntax. Rules of syntax are important not only in linguistics, the study of natural languages, but also in the study of programming languages. 11.3 Phrase Structure Grammars Before, we give a formal definition of a grammar, we introduce a little terminology. Definition 1 A vocabulary (or alphabet) V is a finite, non-empty set of elements called symbols. A word (or sentence) over V is a string of finite length of elements of V. The empty string or null string denoted by
is the string containing no symbols. The set of all words over V is denoted by V*. A language over V is a subset of V*. Note that
, the empty string, is the string containing no symbols. It is different from , the empty set. It follows that [
] is the set containing exactly one string, namely, the empty string. Definition 2 A phrase structure grammar G = {V, T, S, P} consists of a vocabulary V, a subset T of V consisting of terminal symbols, a start symbol S from V, and a finite set of productions P. The set V – T is denoted by N. Elements of N are called non-terminal symbols. Every production in p must contain at least one non-terminal on its left side. Example 1: Let G = {V, T, S, P} where, v = {a, b, A, B, S}, T = {a, b}, S is the start symbol and P = {S  ABa, A  BB, B  ab, AB  b} CU IDOL SELF LEARNING MATERIAL (SLM)

198 Discrete Mathematical Structures G is an example of a phrase structure grammar. We will be interested in the words that can be generated by the productions of a phrase structure grammar. Definition 3 Let G = {V, T, S, P} be a phrase structure grammar, let wo = lZor (i.e., the concatination of l, Z0 and r) and w1 = lZ, r be strings over V. If Z0  Z1 is a production of G, we say that w1 is directly derivable from w0 and we write w0  w1. If w0, w1, w2, ...., wn are from w0 and we write w0, w1, w2, ... wn are from w0 and we write w0*  wn. The sequence of steps used to obtain wn from w0 is called a derivation. Example 2: The string Aaba is directly derivable from ABa in the grammar in Example 1 because B  ab is a production in the grammar. The string abababa is derivable from ABa because ABa  Aaba  BBaba  Bababa  abababa, using the productions B  ab, A  BB, B  ab and B  ab in succession. Definition 4 Let G = {V, T, S, P) be a phrase structure grammar. The language generated by G (or the language of G), denoted by L(G), is the set of all strings of terminals that are derivable from the starting state S. In other words, L(G) = {w T*/S*  w} In Example 3 and Example 4, we find the language generated by a phrase structure grammar. Example 3: Let G be the grammar with vocabulary. V = {S, A, a, b}, set of terminals T = {a, b}, starting symbol S, and productions. p = {S  aA, S  b, A  aa} what is L(G) the language of the grammar? CU IDOL SELF LEARNING MATERIAL (SLM)

State Machine 199 Solution: From the start state S we can derive aA using the production S  aA. we can also use the production S  b to derive b. from aA production A  aa can be used to derive aaa. No additional words can be derived. Hence, L(G) = {b, aaa}. Example 4: Let G be the grammar with vocabulary V = {S, 0, 1}, set of terminals T = {0, 1} Starting symbol S, and Productions P = {S,  11S, S  O}, what is L(G), the language of this grammar? Solution: From S, we can derive 0 using S  O, or 11S using S  11S. From 11S, we can derive either 110 or 1111S. From 1111S, we can derive 1111O and 111111S. At any stage of a derivation, we can either add two 1S at the end of the string or terminate the derivation by adding a 0 a the end of the string. We summarise that L(G) = {0, 110, 11110, 1111110 }, the set of all strings that begin with an even number of 1s and end with a 0. This can be proved using an inductive argument that shows that after n production have been used, the only strings of terminals generated are those consisting of n – 1 can catenations of 11 followed by 0. Some times a set that is easy to describe can be generated only by a complicated grammar. Example 5: One grammar that generates the set {0n 1n 2n/n = 0, 1, 2, 3, ...} is G = {V, T, S, P} with V = {0,1, 2, S, A, B, C}; T = {0, 1, 2}. Starting state S: and productions S  C, C  OCAB, S 
, BA  AB, OA  O1, 1A  11, 1B  12, and 2B  22. CU IDOL SELF LEARNING MATERIAL (SLM)

200 Discrete Mathematical Structures 11.4 Regular Expression and Regular Language 11.4.1 Regular Expression Regular expressions are used to denote regular languages. An expression is regular if:
 is a regular expression for regular language .
 is a regular expression for regular language {}.
If a   ( represents the input alphabet) a regular expression with language {a}.
If a and b are regular expression, a + b is also a regular expression with language {a, b}.
If a and b are regular expression, ab (concatenation of a and b) is also a regular.
If a is regular expression, a* (0 or more times a) is also regular. 11.4.2 Regular Languages A language is regular if it can be expressed in terms of regular expression. Regular Expression Regular Language 1. Set of Vovels (a  e ,  o  u) {a, c, i, o u} 2. A followed by o or more b (a, b*) {a, ab, abb, abbb, abbbb ...} 3. Any number of vovels v*.c* (where v – values and c – {e, a, aou, aiou, b, abcd, ...} followed by any number of consonants) where e represent empty string consonants (in case 0 vowels and 0 consonants) 11.5 FINITE-STATE AUTOMATA (Designing a Finite-State Automata) We can construct a finite-state automation that recognizes a given sold strings by carefully adding states and transitions and determining which of these states should be final states. When appropriate, we include states that can keep track of some of the properties of the input string, providing the finite state automaton with limited memory. CU IDOL SELF LEARNING MATERIAL (SLM)

State Machine 201 Finite State Automata We can define finite-state machine with no output. Such machines are also called finite-state automata. Example 7: State f Input S0 01 S1 S0 S1 S2 S0 S2 S3 S0 S0 S2 S1 Fig. 11.1 State diagram for finite-state automation Definition A finite-state automation M = (S, I, f, S0, F) consists of a finite set S of states, a finite input alphabet I, a transition function f that assigns a next state to every pair of state and input (so that f, CU IDOL SELF LEARNING MATERIAL (SLM)

202 Discrete Mathematical Structures S, Y, I  S), an initial or start state S0 and a subset F of S consisting of final (or accepting states) we can represent finite-state automata using either state table or state diagrams. Final states are indicated in state diagrams by using double circles. 11.6 Finite State Machine A finite-state machine M = (S, I, O, f, g, S0) consists of a finite set S of states, a finite input alphabet I, a finite output alphabet O, a transition function f that assigns to each state and input pair a new state, an output function g that assigns to each state and input pair an output, and an initial state S0. Example 8: Construct the state diagram for the finite state machine with the state table shown in table. State f g Input Input S0 01 01 S1 S1 S0 10 S2 S3 S0 11 S3 S1 S2 01 S2 S1 00 CU IDOL SELF LEARNING MATERIAL (SLM)

State Machine 203 Fig. 11.2 Example 9: Construct the state table for the finite state machine with the state diagram shown in figure. Fig. 11.3 CU IDOL SELF LEARNING MATERIAL (SLM)

204 Discrete Mathematical Structures State f g 0101 S0 S1 S3 1 0 S1 S1 S2 1 1 S2 S3 S4 0 0 S3 S1 S0 0 0 S4 S3 S4 0 0 Example 10: Find the output string generated by the finite-state machine if the input string is 101011 Fig. 11.4 Input 1 0 1 0 1 1 – State S0 S3 S1 S2 S3 S0 S3 Output 0 0 1 0 0 0 – The output obtained is 001000. The successive states and outputs are shown in table. CU IDOL SELF LEARNING MATERIAL (SLM)

State Machine 205 11.7 Summary of the Unit
A finite state machine is a mathematical abstraction used to design algorithms. In simple terms, a state machine will read a series of inputs. When it reads an input it will switch to a different state.
The state machines we’ve looked at so far are all deterministic state machines. From any state there is only one transition for any allowed input. In other words there aren’t two paths leading out of a state when you read the letter a. At first this sounds silly to even make this distinction.
Non-deterministic finite state machines are finite state machines where a given input from a particular state can lead to more than one different state. For example, let us say we want to build a finite state machine that can recognize strings of letters that start with a and are then followed by zero or more occurrences of the letter b or zero or more occurrences of the letter c terminated by the next letter of the alphabet.
Regular expressions and finite state machines are functionally equivalent. Anything you can accept or match with a regular expression can be accepted or matched with a state machine.
Turing Machines are computationally complete and anything that can be computed can be computed on a Turing Machine. Since a Turing Machine can write as well as read from the paper tape, it is not limited to a finite number of states. The paper tape can be assumed to be infinite in length. Turing Machines give us an imaginary mechanical device that lets us visualize and understand how the computational process works. It is particularly useful in understanding the limits of computation. If there is interest I’ll do another article on Turing Machines in the future. 11.8 Key Words/Abbreviations
Finite State machine- a computation model that can be implemented with hardware or software and can be used to simulate sequential logic and some computer programs. CU IDOL SELF LEARNING MATERIAL (SLM)

206 Discrete Mathematical Structures
A Deterministic finite automaton (DFA) is described by a five-element tuple: (Q, , , q0, F). Q = a finite set of states Sigma  = a finite, nonempty input alphabet Delta = a series of transition functions q0 = the starting state F = the set of accepting state
A Non Deterministic finite automaton (NDFA or NFA) is described by a five-element tuple: (Q, , , q0, F). Q = a finite set of states Sigma  = a finite, nonempty input alphabet Delta = a series of transition functions q0 = the starting state F = the set of accepting states 11.9 Learning Activity 1. What is Machine Language? ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. State the different regular expressions used in machine language. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- CU IDOL SELF LEARNING MATERIAL (SLM)

State Machine 207 11.10 Unit End Questions (MCQ and Descriptive) A. Descriptive Types Questions 1. Give a phrase - structure grammar to generates the set {0n 1n/n = 0, 1, 2, ...}. 2. Find a phrase structure grammar to generates the set {0m 1n/m and n are non-negative integers}. 3. Let L – {a2, ab} and M = {a, ab, b2} be language over A = {a, b}. Find (a) LM (b) ML 4. Let M be the finite state, machine with the state table given following. FAB S0 S2, x S1, z S1 S2, x S3, y S2 S2, y S1, z S3 S3, y S0, x (a) Find the input set A, the state get S, the output set Z, and the initial state of M. (b) Draw the state diagram D = D(M) of M. (c) Find the output word v, if the input is the word w = a2b2 ab2a2b. B. Multiple Choice/Objective Type Questions 1. How many strings of length less than 4 contains the language described by the regular expression (x + y) * y(a + ab) * ? (a) 7 (b) 10 (c) 12 (d) 11 2. A language is regular if and only if (a) accepted by DFA (b) accepted by PDA (c) accepted by LBA (d) accepted by Turing Machine CU IDOL SELF LEARNING MATERIAL (SLM)

208 Discrete Mathematical Structures 3. Regular Grammar is (b) non-context free Grammar (a) context free grammar (d) None of these. (c) english Grammar (b) Type 2 language 4. Regular expression are: (d) Type 3 language (a) Type 1 language (c) Type 0 language (b) Inostersection (d) All of the mentioned. 5. Regular expressions are closed under (a) Union (c) Kleen Star Answers 1. (d), 2. (a), 3. (a), 4. (c), 5. (d) 11.11 References References Books: 1. http://www.xcprod.com/titan/state_machine_desc_033.pdf 2. https://ptolemy.berkeley.edu/books/Systems/chapters/FiniteStateMachines.pdf Web Resources: 1. https://brilliant.org/wiki/finite-state-machines/ 2. https://www.includehelp.com/basics/finite-automata.aspx 3. http://www.cs.utsa.edu/~bylander/cs2233/languageshandout 4. https://en.wikibooks.org/wiki/Discrete_Mathematics/Finite_state_automata CU IDOL SELF LEARNING MATERIAL (SLM)