Example 2.3.2: Let us construct a regular expression for the language accepted by the deterministic finite automaton of

[answerhappygod]

Example 2 3 2 Let Us Construct A Regular Expression For The Language Accepted By The Deterministic Finite Automaton Of 1 (37.97 KiB) Viewed 33 times

Example 2 3 2 Let Us Construct A Regular Expression For The Language Accepted By The Deterministic Finite Automaton Of 2 (27.41 KiB) Viewed 33 times

Example 2 3 2 Let Us Construct A Regular Expression For The Language Accepted By The Deterministic Finite Automaton Of 3 (23.94 KiB) Viewed 33 times

Example 2 3 2 Let Us Construct A Regular Expression For The Language Accepted By The Deterministic Finite Automaton Of 4 (13.99 KiB) Viewed 33 times

Example 2.3.2: Let us construct a regular expression for the language accepted by the deterministic finite automaton of Figure 2-15. This automaton accepts the language {w € {a,b}* : w has 3k + 1 b's for some k e N}. Carrying out explicitly the construction of the proof of the if part can be very tedious (in this simple case, thirty-six regular expressions would have to be constructed!). Things are simplified considerably if we assume that the nonde- terministic automaton M has two simple properties:

2.3: Finite Automata and Regular Expressions 81 93 b b a a b 91 92 Figure 2-15 (a) It has a single final state, F = {f}. (b) Furthermore, if (q, u,p) E A, then a 7 f and p #s; that is, there are no transitions into the initial state, nor out of the final state.

95 O e 95 o 93 e 93 b b a*b, 6 94 92 44 ba*b e b 92 a a (a) (b) a Uba*ba*b 95 94 a*b & e 94 a*b(a Uba*ba*b)* O) 93 95 (c) (d)

Apply the construction in Example 2.3.2 to obtain regular expression corresponding to the following finite automaton. Show your construction process. a b b a