Properties of Regular Expressions

xnnfcf frefnrfnk dfrefnr

1. Costas Busch - LSU 1 Properties of Regular Languages

2. Costas Busch - LSU 2 Concatenation: Star: Union: Are regular Languages For regular languages and we will prove that: Complement: Intersection: Reversal:

3. Costas Busch - LSU 3 We say Regular languages are closed under Concatenation: Star: Union: Complement: Intersection: Reversal:

4. Costas Busch - LSU 4 NFA Equivalent NFA A useful transformation: use one accept state 2 accept states 1 accept state

5. Costas Busch - LSU 5 NFA Equivalent NFA Single accepting state In General

6. Costas Busch - LSU 6 NFA without accepting state Add an accepting state without transitions Extreme case

7. Costas Busch - LSU 7 Regular language Single accepting state NFA Single accepting state Regular language NFA Take two languages

8. Costas Busch - LSU 8 Example

9. Costas Busch - LSU 9 Union NFA for

10. Costas Busch - LSU 10 NFA for Example

11. Costas Busch - LSU 11 Concatenation NFA for change to regular state

12. Costas Busch - LSU 12 NFA for Example

13. Costas Busch - LSU 13 Star Operation NFA for or

14. Costas Busch - LSU 14 Example NFA for

15. Costas Busch - LSU 15 Reverse NFA for 1. Reverse all transitions 2. Make the initial state accept state and the accept state initial state

16. Costas Busch - LSU 16 Example

17. Costas Busch - LSU 17 Complement 1. Take the DFA that accepts 2. Make accept states regular and vice-versa

18. Costas Busch - LSU 18 Example

19. Costas Busch - LSU 19 NFAs cannot be used for complement Make accept states regular and vice-versa NFA NFA it is not the complement

20. Costas Busch - LSU 20 Same example with DFAs Make accept states regular and vice-versa DFA DFA it is the complement

21. Costas Busch - LSU 21 Intersection regular regular We show regular

22. Costas Busch - LSU 22 DeMorgan’s Law: regular, regular regular, regular regular regular regular

23. Costas Busch - LSU 23 Example regular regular regular

24. Costas Busch - LSU 24 for for DFA DFA Construct a new DFA that accepts Machine Machine simulates in parallel and Another Proof for Intersection Closure

25. Costas Busch - LSU 25 States in State in State in

26. Costas Busch - LSU 26 transition transition DFA DFA New transition DFA

27. Costas Busch - LSU 27 initial state initial state New initial state DFA DFA DFA

28. Costas Busch - LSU 28 accept state accept states New accept states DFA DFA DFA Both constituents must be accepting states

29. Costas Busch - LSU 29 Example:

30. Costas Busch - LSU 30 DFA for intersection

31. Costas Busch - LSU 31 Construction procedure for intersection 1. Build Initial State 2. For each new state and for each symbol add transition to either an existing state or create a new state and point to it 3. Repeat step 3 until no new states are added 4. Designate accept states

32. Costas Busch - LSU 32 Automaton for intersection initial state

33. Costas Busch - LSU 33 Automaton for intersection add transition and new state for symbol a

34. Costas Busch - LSU 34 Automaton for intersection add transition and new state for symbol b

35. Costas Busch - LSU 35 Automaton for intersection Repeat until no new states can be added

36. Costas Busch - LSU 36 Automaton for intersection add Accept state accept state for accept state for

37. Costas Busch - LSU 37 simulates in parallel and accepts string if and only if: accepts string and accepts string Intersection DFA :