theoryofautomataandformallanguagesunit21-161231042659.pptx

mataandformallanguagesunit21-161231042659.pptx

1. A  regular expression (sometimes called a  rational expression )is, in computer science and formal languages theory, a sequence of characters that define a search pattern. usually this pattern is then used by  in string searching algorithm "find" or "find and replace" operations on strings. 2. REGULAR EXPRESSION AND LANGUAGES Abhimanyu Mishra(CSE) JETGI 4/26/2024 1

2. 2.1 Definition of Regular Expression: The set of regular expression of defined by the following rules: ( i ) Every letter of ∑ can be made into regular expression, null string,€ itself is a regular expression. (ii) If r 1 and r 2 are regular expression, then (a) (r 1 ) (b) r 1 r 2 (c) r 1 +r 2 (d) r 1 * (e) r 1 + are also regular expression (iii) Nothing else is regular expression. 4/26/2024 Abhimanyu Mishra(CSE) JETGI 2

3. 2.1.1 Building Regular Expression The constants ϵ(null string) and ɸ(empty set) are regular expression, denote the languages {ϵ} and ɸ, respectively. That is, L( ϵ) = {ϵ} , and L(ɸ)= ɸ. If a is any symbol, then a is regular expression. This expression denotes the language {a}. That is L(a)={a}. (iii) A variable, usually capitalized and such as L is a variable, representing any language. 4/26/2024 Abhimanyu Mishra(CSE) JETGI 3

4. 2.2 Construction of FA for Regular Expression The Expression is r+s for some smaller expression r and s. The following automation serves, where R is automation for r and S is automation for s. That is, starting at the new start state, We can go to the start state of either the automation for r or the automation for S So L(r) and L(s) ϵ ϵ Start ϵ ϵ 4/26/2024 Abhimanyu Mishra(CSE) JETGI 4 R S

5. 2.The expression rs for some smaller expression r and s. The automation for the concatenation is …………. Start ϵ ϵ ϵ 3. The expression is r* for some smaller expression r. Then we use automation of ………. ϵ Start ϵ ϵ ϵ 4/26/2024 Abhimanyu Mishra(CSE) JETGI 5 R S R

6. Arden's Theorem In order to find out a regular expression of a Finite Automaton, we use Arden’s Theorem along with the properties of regular expressions. Statement − Let P and Q be two regular expressions. If P does not contain null string (I) R = Q + RP has a unique solution, (ii) R = QP * 4/26/2024 Abhimanyu Mishra(CSE) JETGI 6

7. Proof − R = Q + (Q + RP)P [After putting the value R = Q + RP] = Q + QP + RPP When we put the value of R recursively again and again, we get the following equation − R = Q + Q P + QP 2 + QP 3 ….. R = Q ( ϵ + P + P 2 + P 3 + …. ) R = QP * [As P* represents ( ϵ + P + P 2 + P 3 + ….) ] proved. 4/26/2024 Abhimanyu Mishra(CSE) JETGI 7

8. Assumptions for Applying Arden’s Theorem − The transition diagram must not have NULL transitions It must have only one initial state: Method Step 1 − Create equations as the following form for all the states of the DFA having n states with initial state q 1 . q 1 = q 1 R 11 + q 2 R 21 + … + q n R n1 + ϵ q 2 = q 1 R 12 + q 2 R 22 + … + q n R n2 ……………………………………………………………. ……………………………………………………………. q n = q 1 R 1n + q 2 R 2n + … + q n R nn R ij represents the set of labels of edges from q i to q j , if no such edge exists, then R ij = ɸ Step 2 − Solve these equations to get the equation for the final state in terms of R ij 4/26/2024 Abhimanyu Mishra(CSE) JETGI 8

9. Example 1: Construct a regular expression corresponding to the automata given below − b a b b a a 4/26/2024 Abhimanyu Mishra(CSE) JETGI 9 q2 q1 q3

10. Solution: Here the initial state is q 2 and the final state is q 1 . The equations for the three states q 1 , q 2, q 3 q 1 = q 1 a + q 3 a + ϵ (ϵ move is because q 1 is the initial state) q 2 = q 1 b + q 2 b + q 3 b q 3 = q 2 a Now, we will solve these three equations − q 2 = q 1 b + q 2 b + q 3 b = q 1 b + q 2 b + (q 2 a)b (Substituting value of q 3 ) = q 1 b + q 2 (b + ab) = q 1 b (b + ab) * (Applying Arden’s Theorem) 4/26/2024 Abhimanyu Mishra(CSE) JETGI 10

11. q 1 = q 1 a + q 3 a + ϵ = q 1 a + q 2 aa + ϵ ( Substituting value of q 3 ) = q 1 a + q 1 b(b + ab * ) aa + ϵ ( Substituting value of q 2 ) = q 1 (a + b(b + ab)* aa ) + ϵ = ϵ ( a+ b(b + ab)* aa ) * = (a + b(b + ab)* aa ) * Hence, the regular expression is (a + b(b + ab)* aa ) * . 4/26/2024 Abhimanyu Mishra(CSE) JETGI 11