Decision properties of reular languages

Decision properties of reular languages.Different Problems in Decision Properties

1. Decision Properties Of Regular Languages Guide : Prof. Saraswati Patil Somnath More(08) Vishwajeet Mote(10) Akanksha Pokale(68) Amit Puranik(79)

2. Content Introduction Representation of regular languages Decision properties Why decision properties? Decision problems Applications Conclusion References

3. Introduction Regular Languages: A language that can be defined by regular expressions and are accepted by finite automata. L = {abb, aabb, aaabb, ……..} Language Properties: Decision properties and Closure properties.

4. Representation of Regular Languages Representations can be formal or informal. Example of Formal Representation : Regular expressions and Deterministic finite automata defining it. Example of Informal Representation : Logical or Prose statement about strings:- {0^n1^n| n is a nonnegative integer}.

5. Decision Properties Decision property for a class of languages is an algorithm that takes a formal description of a language. E.g : Is given language L empty?

6. Why Decision Properties? We might want a “smallest” representation for a language. If we can’t decide “Are the languages same?” then we can’t find a “smallest”.

7. Continued... When we talk about protocols represented as DFA’s we noted that important properties of a good protocol were related to the language of the DFA. Example: “Does the protocol terminate?” = “Is the language finite?” Example: “Can the protocol fail?” = “Is the language nonempty?”

8. Problem Types Decidable Problem : We can always construct a corresponding algorithm the can answer the problem correctly .It answer maybe “Yes” or “NO”.eg.Prime numbers in the range of 1000 to 2000 eg.Are Two Regular Languages L and M Equivalent. Undecidable Problem : The problems for which we can’t construct an algorithm that can answer the problem correctly in finite time are termed as Undecidable Problems. eg. Whether a CFG generates all the strings or not?. Semi Decidable Problem :Eg::Turing Recognisable Problems. .

9. Decision Properties Emptiness and Non emptiness Finiteness and Infiniteness Membership Equivalence

10. Emptiness and Non Emptiness To check whether a given FA accepts empty language or non-empty language. Steps to check emptiness: Select the state that cannot be reached from the initial states & delete them (remove unreachable states).

11. Emptiness and Non Emptiness 2) If the resulting machine contains at least one final states, so then the finite automata accepts the non-empty language. 3)If the resulting machine is free from final state, then finite automata accepts empty language.

12. Finiteness and Infiniteness It states that the language accepted by a given FA is finite or not. Steps: Select the state that cannot be reached from the initial state & delete them (remove unreachable states).

13. Finiteness and Infiniteness 2) Select the state from which we cannot reach the final state & delete them (remove dead states). 3) If the resulting machine contains loops or cycles then the finite automata accepts infinite language. 4) If the resulting machine do not contain loops or cycles then the finite automata accepts infinite language.

14. b a Fig. A Fig. B Fig. C

15. Membership Membership is a property to verify an arbitrary string is accepted by a finite automata or not. It is decidable, because by reading the string if it reaches the final state, then it is a member. Otherwise, if the string halts in a non-final state then it is said to be not a member of the FA.

16. Is string w accepted by given FA? w=01011.

17. Equivalence Steps to identify equivalence: If initial state is final state for one automaton, then in second automaton also initial state must be final state for them to be equivalent. For any pair of states {qi,qj} the transition for the input a ∈ Σ is defined by {qa,qb} where δ {qi,a} = qa and δ {qj,a} = qb. The two automata are not equivalent if for a pair {qa,qb} one is intermediate state and other is final state.

18. Example: A B

19. Continued... States C D (q1,q4) (q1,q4) Both final states (q2,q5) Both intermediate states (q2,q5) (q3,q6) Both intermediate states (q1,q4) Both final states (q3,q6) (q2,q7) Both intermediate states (q3,q6) Both intermediate states (q2,q7) (q3,q6) Both intermediate states (q1,q4) Both final states A and B are equivalent . :

20. Example A B

21. Continued... States C D (q1,q4) (q1,q4) Both final states (q2,q5) Both intermediate states (q2,q5) (q3,q7) Both intermediate states (q1,q6) Here q1 is final state and q6 is intermediate state A and B are not equivalent.

22. Applications Data Validation Data Scraping(Web Scraping), Data Wrangling, simple Parsing The Production Of Syntax Highlighting Systems and many other tasks.

23. Conclusion Regular Languages and their representation. Decision properties and why do we need them. (Emptiness, Equivalence, Finiteness, Membership) Types of problems Applications

24. References https://www.isical.ac.in/~ansuman/flat2018/Closure.pdf https://www.youtube.com/watch?v=9B0i9GuFFwk&t=238s https://www.youtube.com/watch?v=cVWyTYW5oTg https://www.geeksforgeeks.org/closure-properties-of-regular-languages/ https://www.cs.rit.edu/~jmg/courses/cs380/20021/slides/minfa.pdf

25. Guide : Prof. Saraswati Patil Somnath More(08) Vishwajeet Mote(10) Akanksha Pokale (68) Amit Puranik (79) Thank You!