Automata Learning.pdf

CSE322 Formal Languages and Automation Theory Learning School of Computer Science and Engineering  Theory of Computation (TOC) Behind every implementation, there is one theory. Theory gives understanding of concept, Principals, etc… To know, how computer w...

CSE322 Formal Languages and Automation Theory Learning School of Computer Science and Engineering  Theory of Computation (TOC) Behind every implementation, there is one theory. Theory gives understanding of concept, Principals, etc… To know, how computer works?, TOC is behind this. Three pillar of TOC are, (i.e. LAG) – Language – Automata – Grammer  Theory of Computation (TOC) Languages: – Important aspect of any language is symbol. – Symbols are building block of any language. – Symbols are : {a,b,c,d,e,0,1,2,3,4,5……} – Alphabets = Finite set of Symbols Example: Sigma (a,b) – String : Sequence of Alphabets If length of string is 2, then {a,b,aa,ab,bb,ba} If length of string is 3 or 4? Theory of Computation (TOC) – What is language? Collection of all string is called as language. Language can be finite or Infinite Example: 1) L1 : Collection of all strings of length 3, Sigma (a,b) {aaa,aab,aba,abb,baa,bab,bba,bbb} 2) L2: All the string should start with a and end with a, Sigma (a,b) {aa,aaa,aaaa……...,aba,abbba,……} 3) L3: Length should be 0 Sigma 0 = epsilon Theory of Computation (TOC) – What is Concept of Automata? – It is model or machine. Description: If we want to find any string from given any language, then Its possible when strings are finite, as we can store same, but in case of infinite, its difficult. To resolve this issue, Automata take place. Mechanism – Finite Automata – Pushdown Automata – Linear bound Automata – Turing Machine Theory of Computation (TOC) – Power of Sigma – If Sigma {a,b}, Sigma power 0: Set of all strings with the length “0” – Answer: Epsilon OR Lambda (i.e. Null String) Sigma power 1: Set of all strings with the length “1” – Answer: {a,b} Sigma power 2: Set of all strings with the length “2” – Answer:{aa,ab,ba,bb}... Sigma power n: Set of all strings with the length “n” Sigma * : Kleene Clouser (i.e. Infinite String) Theory of Computation (TOC) – Sigma + : Positive Clouser – Sigma + = Sigma * - Sigma 0 = Sigma * - Epsilon Topics  Acceptability of a String by a Finite Automaton  Transition Graph and Properties of Transition Functions Finite Automaton Input String Output “Accept” Finite or Automaton “Reject” Transition Graph a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 initial accepting state state transition state Initial Configuration Input String a b b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Reading the Input a b b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 a b b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 a b b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 a b b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Input finished a b b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 accept Rejection a b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 a b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 a b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 a b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Input finished a b a a, b reject q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Another Rejection  a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4   a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 reject Another Example a a b a a, b q0 b q1 a, b q2 a a b a a, b q0 b q1 a, b q2 a a b a a, b q0 b q1 a, b q2 a a b a a, b q0 b q1 a, b q2  Input finished a a b a a, b accept q0 b q1 a, b q2 Rejection Example b a b a a, b q0 b q1 a, b q2 b a b a a, b q0 b q1 a, b q2 b a b a a, b q0 b q1 a, b q2 b a b a a, b q0 b q1 a, b q2 Input finished b a b a a, b q0 b q1 a, b q2 reject Definition An automaton is defined as a system where energy, materials and information are transformed, transmitted and used for performing some functions without direct participation of man. Input alphabet   a, b a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Set of States States Q  q0 , q1, q2 , q3 , q4 , q5  a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Initial State a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Accepting State F Set of Accepting States F  q4  a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Formal Definition Finite Automaton (FA) M  Q, ,  , q0 , F  Q : set of states  : input alphabet  : transition function q0 : initial state F : set of accepting states DESCRIPTION OF A FINITE AUTOMATON  MCQ There are ________ tuples in finite state machine. a) 4 b) 5 c) 6 d) unlimited  Types of Automaton An automaton in which the output depends only on the input is called an automaton without a memory. An automaton in which the output depends on the states as well. is called automaton with a finite memory. An automaton in which the output depends only on the states of the machine is called a Moore machine. An automaton in. which the output depends on the state as well as on the input at any instant of time is called a Mealy machine  An Automaton Basics  Block Diagram of Finite Automaton Diagram Transition System Example  Class work 110011 110110 Example Table Form Cont.  Class Work Check for the 101101 11111 000000 Input alphabet (Diagram Based)   a, b a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4  Cont. Set of States Q  q0 , q1, q2 , q3 , q4 , q5  a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Initial State a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Accepting State F Set of Accepting States F  q4  a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Example Input String a b b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Reading the Input a b b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 a b b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 a b b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 a b b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Input finished a b b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 accept Rejection a b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 a b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 a b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 a b a a, b q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Input finished a b a a, b reject q5 a a, b b a b q0 a q1 b q2 b q3 a q4  Class Work abbbaaab bababaa abbaaba  MCQ Which of the following is not a part of 5- tuple finite automata? a) Input alphabet b) Transition function c) Initial State d) Output Alphabet  DFA Deterministic Finite Automata (DFA) It's finite automata with deterministic behavior. In DFA, there is exactly one transition from any state of finite automata for each input symbol. It accepts the string by halting at a final state, and it rejects it by halting at a non-final state.  NFA Non-deterministic Finite Automata (NFA) It's a finite automata that isn't deterministic. In NFA, there are zero or more transitions from any state of finite automata for each input symbol. It accepts the string by halting in a final state, and it rejects the string by halting in a non-final state or in a dead configuration.  DFA and NFA Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata (NFA) are used in fields like machine learning, pattern matching, and formal language recognition and verification. They are fundamental concepts that help design software that can interpret languages and patterns, and even build compilers.  DFA VS NFA Sr. No. DFA NFA 1 DFA stands for Deterministic Finite NFA stands for Nondeterministic Finite Automata. Automata. 2 For each symbolic representation of the No need to specify how does the NFA react alphabet, there is only one state transition according to some symbol. in DFA. 3 NFA can be understood as multiple little DFA can be understood as one machine. machines computing at the same time. 4 DFA is more difficult to construct. NFA is easier to construct. 5 Time needed for executing an input string Time needed for executing an input string is is less. more. 6 All DFA are NFA. Not all NFA are DFA. 7 Epsilon move is not allowed in DFA Epsilon move is allowed in NFA 8 DFA allows only one move for single input There can be choice (more than one alphabet. move) for single input alphabet.  DFA EXAMPLES  Example DFA Description: States: Q = {q0, q1} Alphabet: Σ = {0, 1} Transitions: – δ(q0, 0) = q0 – δ(q0, 1) = q1 – δ(q1, 0) = q1 – δ(q1, 1) = q0 Start State: q0 Accept States: {q1} Question: Does the DFA accept the string "010"?  Answer The DFA processes "010" as follows: Start at q0. Read '0', transition to q0. Read '1', transition to q1. Read '0', transition to q1. The DFA ends in state q1, which is not an accept state, so it does accept "010".  Diagram 0 1 0 0 0 1 q0 q1 1  Diagram 0 1 0 0 0 1 q0 q1 1  Diagram 0 1 0 0 0 1 q0 q1 1  Diagram 0 1 0 0 0 1 q0 q1 1 Accepted  Example DFA Description: States: Q = {q0, q1} Alphabet: Σ = {a, b} Transitions: – δ(q0, a) = q1 – δ(q0, b) = q0 – δ(q1, a) = q1 – δ(q1, b) = q0 Start State: q0 Accept States: {q1} Question: Does the DFA accept the string "ab"?  Answer The DFA processes "ab" as follows: Start at q0. Read 'a', transition to q1. Read 'b', transition to q0. The DFA ends in state q0, which is not an accept state, so it does not accept "ab".  Example DFA Description: States: Q = {q0, q1, q2} Alphabet: Σ = {0, 1} Transitions: – δ(q0, 0) = q1 – δ(q0, 1) = q0 – δ(q1, 0) = q2 – δ(q1, 1) = q0 – δ(q2, 0) = q2 – δ(q2, 1) = q2 Start State: q0 Accept States: {q2} Question: Does the DFA accept the string "0010"?  Answer Yes. The DFA processes "0010" as follows: Start at q0. Read '0', transition to q1. Read '0', transition to q2. Read '1', transition to q2. Read '0', transition to q2. The DFA ends in state q2, which is an accept state, so it accepts "0010".  Example DFA Description: States: Q = {q0, q1, q2} Alphabet: Σ = {a, b} Transitions: – δ(q0, a) = q1 – δ(q0, b) = q0 – δ(q1, a) = q0 – δ(q1, b) = q2 – δ(q2, a) = q2 – δ(q2, b) = q2 Start State: q0 Accept States: {q2} Question: Does the DFA accept the string "abab"?  Answer Yes. The DFA processes "abab" as follows: Start at q0. Read 'a', transition to q1. Read 'b', transition to q2. Read 'a', transition to q2. Read 'b', transition to q2. The DFA ends in state q2, which is an accept state, so it accepts "abab".  Example DFA Description: States: Q = {q0, q1, q2, q3} Alphabet: Σ = {0, 1} Transitions: – δ(q0, 0) = q1 – δ(q0, 1) = q2 – δ(q1, 0) = q3 – δ(q1, 1) = q0 – δ(q2, 0) = q0 – δ(q2, 1) = q3 – δ(q3, 0) = q2 – δ(q3, 1) = q1 Answer: No. The DFA processes "1100" as follows:  Cont. Start State: q0 Accept States: {q0} Question: Does the DFA accept the string "1100"?  Answer No. The DFA processes "1100" as follows: Start at q0. Read '1', transition to q2. Read '1', transition to q3. Read '0', transition to q2. Read '0', transition to q0. The DFA ends in state q0, which is an accept state, so it accepts "1100". NFA/NDFA EXAMPLES Nondeterministic Finite Automaton Alphabet = {a} q1 a q2 a q0 a q3 Alphabet = {a} Two choices q1 a q2 a q0 a q3 Alphabet = {a} Two choices a q1 q2 No transition a q0 a q3 No transition  First Choice a a q1 a q2 a q0 a q3  First Choice a a q1 a q2 a q0 a q3  First Choice a a q1 a q2 a q0 a q3  First Choice a a All input is consumed q1 a q2 “accept” a q0 a q3  Second Choice a a q1 a q2 a q0 a q3  Second Choice a a q1 a q2 a q0 a q3  Second Choice a a q1 a q2 a q0 a No transition: q3 the automaton hangs  Second Choice a a Input cannot be consumed q1 a q2 a q0 a q3 “reject”  Example aa is accepted by the NFA: “accept” q1 a q2 q1 a q2 a a q0 q0 a a q3 q3 “reject” because this computation accepts aa  Rejection example a q1 a q2 a q0 a q3  First Choice a q1 a q2 a q0 a q3  First Choice a “reject” q1 a q2 a q0 a q3  Second Choice a q1 a q2 a q0 a q3  Second Choice a q1 a q2 a q0 a q3  Second Choice a q1 a q2 a q0 a q3 “reject”  Example a is rejected by the NFA: “reject” q1 a q2 a q1 q2 a a q0 q0 a a q3 “reject” q3 All possible computations lead to rejection  Rejection example a a a q1 a q2 a q0 a q3  First Choice a a a q1 a q2 a q0 a q3  First Choice a a a q1 a q2 a q0 a No transition: the automaton hangs q3  First Choice a a a Input cannot be consumed q1 a q2 “reject” a q0 a q3  Second Choice a a a q1 a q2 a q0 a q3  Second Choice a a a q1 a q2 a q0 a q3  Second Choice a a a q1 a q2 a q0 a No transition: q3 the automaton hangs  Second Choice a a a Input cannot be consumed q1 a q2 a q0 a q3 “reject” aaa is rejected by the NFA: “reject” q1 a q2 q1 a q2 a a q0 q0 a a q3 q3 “reject” All possible computations lead to rejection Language accepted: L  {aa} q1 a q2 a q0 a q3  Lambda Transitions q0 a q1  q2 a q3 a a q0 a q1  q2 a q3 a a q0 a q1  q2 a q3 (read head does not move) a a q0 a q1  q2 a q3 a a q0 a q1  q2 a q3 all input is consumed a a “accept” q0 a q1  q2 a q3 String aa is accepted  Rejection Example a a a q0 a q1  q2 a q3 a a a q0 a q1  q2 a q3 (read head doesn’t move) a a a q0 a q1  q2 a q3 a a a q0 a q1  q2 a q3 No transition: the automaton hangs Input cannot be consumed a a a “reject” q0 a q1  q2 a q3 String aaa is rejected Language accepted: L  {aa} q0 a q1  q2 a q3  Another NFA Example q0 a q1 b q2  q3  a b q0 a q1 b q2  q3  a b q0 a q1 b q2  q3  a b q0 a q1 b q2  q3  a b “accept” q0 a q1 b q2  q3   Another String a b a b q0 a q1 b q2  q3  a b a b q0 a q1 b q2  q3  a b a b q0 a q1 b q2  q3  a b a b q0 a q1 b q2  q3  a b a b q0 a q1 b q2  q3  a b a b q0 a q1 b q2  q3  a b a b q0 a q1 b q2  q3  a b a b “accept” q0 a q1 b q2  q3   Language accepted L  ab, abab, ababab,...   ab q0 a q1 b q2  q3   Example NFA Description: States: Q = {q0, q1, q2} Alphabet: Σ = {a, b} Transitions: – δ(q0, a) = {q1, q2} – δ(q0, b) = {q0} – δ(q1, a) = {q1} – δ(q1, b) = {q0, q2} – δ(q2, a) = ∅ – δ(q2, b) = {q2} Start State: q0 Accept States: {q2} Question: Does the NFA accept the string "aab"?  Example NFA Description: States: Q = {q0, q1, q2} Alphabet: Σ = {a, b} Transitions: – δ(q0, a) = {q0, q1} – δ(q0, b) = {q2} – δ(q1, a) = {q2} – δ(q1, b) = ∅ – δ(q2, a) = {q2} – δ(q2, b) = {q1} Start State: q0 Accept States: {q2} Question: Does the NFA accept the string "baa"?  Example NFA Description: States: Q = {q0, q1, q2, q3} Alphabet: Σ = {a, b} Transitions: – δ(q0, a) = {q1} – δ(q0, b) = {q0, q2} – δ(q1, a) = {q3} – δ(q1, b) = {q1} – δ(q2, a) = ∅ – δ(q2, b) = {q3} – δ(q3, a) = {q3} – δ(q3, b) = ∅ Start State: q0 Accept States: {q3} Question: Does the NFA accept the string "abbb"?  Example NFA Description: States: Q = {q0, q1, q2, q3} Alphabet: Σ = {a, b} Transitions: – δ(q0, a) = {q0, q1} – δ(q0, b) = {q2} – δ(q1, a) = {q3} – δ(q1, b) = {q1, q2} – δ(q2, a) = {q1} – δ(q2, b) = {q3} – δ(q3, a) = {q0} – δ(q3, b) = ∅ Start State: q0 Accept States: {q3} Question: Does the NFA accept the string "abb"?  Example NFA Description: States: Q = {q0, q1, q2} Alphabet: Σ = {a, b} Transitions: – δ(q0, a) = {q1} – δ(q0, b) = {q2} – δ(q1, a) = {q0, q1} – δ(q1, b) = {q2} – δ(q2, a) = ∅ – δ(q2, b) = {q1, q2} Start State: q0 Accept States: {q1} Question: Does the NFA accept the string "aab"?  Moore and Mealy Machine Basics: DFA and NFA are the finite automata without Output, where Moore and Mealy are the finite automata with output. Moore machine always give output in +1 form, if length of string is n then output will be n+1. Example: Input String = 11010 Then Output will be Length of String + 1 = 5+1 =6  Cont. Mealy machine always give output in +0 form, if length of string is n then output will be n. Example: Input String = 11010 Then Output will be Length of String = 5  Moore Machines Moore Machines are finite state machines with output value and its output depends only on the present state. It can be defined as (Q, q0, ∑, , δ, λ) where: Q is a finite set of states. q0 is the initial state. ∑ is the input symbol. is the output symbol. δ is the transition function which maps Q×∑ → Q. λ is the output function which maps Q →.  Cont. Moore Machine 0 0 1 0 q2/b q0/a q1/b 1 1  Cont. λ:Q= (What will be Output Corresponding to states?)  Cont. If Input string 101101 Then Output will be 101101= 6 + 1 =7 0 0 1 0 q2/b q0/a q1/b 1 1 Output = abbbaab  Cont. Class Work: Input String are as mentioned below, what will be output? 1. 11101000 2. 1101 3. 0000110101 4. 0001101010 5. 1010101010 6. 101011110011  Mealy Machines Mealy machines are also finite state machines with output value and their output depends on the present state and current input symbol. It can be defined as (Q, q0, ∑, , δ, λ’) where: Q is a finite set of states. q0 is the initial state. ∑ is the input symbol. is the output symbol. δ is the transition function which maps Q×∑ → Q. ‘λ’ is the output function that maps Q×∑→.  Cont. Mealy Machine a/0 a/1 b/1 q0 q1 b/0  Cont. λ : Q x ∑ -> (What will be Output Corresponding to states?)  Cont. If Input string abbab Then Output will be abbab = 5 Output = 01001  Cont. Class Work: Input String are as mentioned below, what will be output? 1. aaababababa 2. bbbbaaaa 3. bababaaab 4. babababbbaa 5. babaababaaa 6. ababababaabb  Regular Language A regular language is a language that can be expressed with a regular expression or a deterministic or non-deterministic finite automata or state machine. A language is a set of strings which are made up of characters from a specified alphabet, or set of symbols. Example: L1 = {a,aa,aaa,aaaa,aaaaa,aaaaaa,aaaaaaa…..} L2 = {ab,abab,ababab,abababab…….}  Regular Expression We use regular expression to represent regular languages. Let, R be the regular expression over alphabet Σ, if R is, – ε is regular expression, denoting a set {ε} R = ε and L(R) = {ε} – Φ is regular expression, denoting a set {Φ} R = Φ and L(R) = { } – For each symbol a ∈ Σ, here a is regular expression, denoting a set {a} R = a and L(R) = {a}  Cont. R1 ∪ R2 = Regular Expression (Union), this can also represent as R1 + R2 R1 x R2 = Regular Expression (Concatenation) a* is regular expression – a*is kleene closer, it contains all strings. – a* = {ε,a,aa,aaa,aaaa,aaaaa,aaaaaa……} NFA to DFA CONVERSIONS  Example Create an NFA, in which 2nd last bits of binary string will be 1. 1 0,1 q0 q1 q2 0,1 State 0 1 q0 q0 q0.q1 q1 q2 q2 q2 - -  Cont. State 0 1 q0 q0 q0q1 q0q1 q0q2 q0q1q2 q0q2 q0 q0q1 q0q1q2 q0q2 q0q1q2  Cont. 0 1 q0 q0q1 1 0 1 0 q0q2 q0q1q2 1 0  Example State 0 1 →q0 q0 q1 q1 {q1, q2} q1 *q2 q2 {q1, q2}  Cont. State 0 1 →q0 q0 q1 q1 {q1, q2} q1 *q2 q2 {q1, q2} State 0 1 →[q0] [q0] [q1] [q1] [q1, q2] [q1] *[q2] [q2] [q1, q2] *[q1, q2] [q1, q2] [q1, q2] Cont.  Example State 0 1 →q0 {q0, q1} {q1} *q1 ϕ {q0, q1}  Cont. State 0 1 →[q0] [q0, q1] [q1] *[q1] ϕ [q0, q1] *[q0, q1] [q0, q1] [q0, q1] Cont.  Minimization of DFA Minimization of DFA means reducing the number of states from given FA. Thus, we get the FSM(finite state machine) with redundant states after minimizing the FSM. DFA minimization stands for converting a given DFA to its equivalent DFA with minimum number of states. DFA minimization is also called as Optimization of DFA and uses partitioning algorithm.  Example DFA Minimization a a q0 q1 b q3 a b a b q2 q4 a a b b b q6 q5 b a Cont. State a b q0 q1 q2 q1 q3 q4 q2 q3 q5 q3 q3 q1 q4 q4 q5 q5 q5 q4 q6 q2 q6  Cont. Transition Table Minimization Remove unreachable state from initial state. q6 is unreachable state from initial state qo. Therefor, q6 eliminated from the DFA.  Cont. Transition Table Minimization Now convert all state in equivalent group. One group will be final states and another one will be non-final states. G1 : {q0,q1,q2} & G2: {q3,q4,q5} G11:{q0} G12: {q1,q2} & G21:{q3} G22: {q4,q5} G111:{q0} G112: {q1,q2} & G211:{q3} G212: {q4,q5} So, at the end, we minimized DFA (From 7 states to 4 states).  Cont. Minimized DFA a q0 q3 a a,b b a,b b q1q2 q4q5 REGULAR LANGUAGE & EXPRESSION  Regular Language A regular language is a language that can be expressed with a regular expression. – ε is regular expression, denoting a set {ε} R = ε and L(R) = {ε} – Φ is regular expression, denoting a set {Φ} R = Φ and L(R) = { } A language is a set of strings which are made up of characters from a specified alphabet, or set of symbols. Example: L1 = {a,aa,aaa,aaaa,aaaaa,aaaaaa,aaaaaaa…..} L2 = {ab,abab,ababab,abababab…….}  Cont. R1 ∪ R2 = Regular Expression (Union), this can also represent as R1 + R2 R1 x R2 = Regular Expression (Concatenation) a* is regular expression – a*is kleene closer, it contains all strings including null. – a* = {ε,a,aa,aaa,aaaa,aaaaa,aaaaaa……} – a+ = a*- ε = aa* is positive closer, it contains all strings excluding null. – a+ = {a,aa,aaa,aaaa,aaaaa,aaaaaa,aaaaaaa……}  Cont. If Σ (a,b) then Regular expression for Finite regular language can be… Language Expression No string: { } Φ Length 0: {ε} ε Length 1: {a,b} (a+b) Length 2: {aa,ab,ba,bb} Either aa+ab+ba+bb OR (a+b)(a+b) Length 3: {aaa,aab,aba……} (a+b)(a+b)(a+b) At most 1: {ε,a,b} (ε+a+b) At most 2:{εε, εa, εb,aε,aa,ab,bε,ba,bb} (ε+a+b) (ε+a+b) Not more than 2 b’s and 1 a’s: {ε, a,b, ab, ε + a + b + b (a+b) ba, bb, abb, bab……}  Cont. If Σ (a,b) then Regular expression for Infinite regular language can be… Language Expression All string having single “b” a* b a* All string having at least one “b” (a+b)* b (a+b)* All string having at least “bbbb” as (a+b)* bbbb (a+b)* substring All string having at least “ab” (a+b)* ab (a+b)* All string starting with “ba” ba (a+b)* All string beginning and ending with “a” a (a+b)* a All string containing “a” (a+b)* a (a+b)* All string starting and ending with (a (a+b)* b + b (a+b)* a) different symbol