introductory Discrete structure workshop.pptx

workshop for students

1. http://www.free-powerpoint-templates-design.com Discrete Structure Support Workshop for Proficiency Exam CS Program 2024

2. Workshop Agenda Deterministic Finite State Automata Regular Expressions Context Free Grammar Proof Techniques and their Structures (direct proof, proof by contradiction, and induction ) Recurrence Relations Modular Arithmetic-based Computations Recursion and its use

3. Deterministic Finite State Automata(DFA)

4. Deterministic Finite State Automata(DFA ) An informal definition : A diagram with a finite number of states represented by circles An arrow points to one of the states, the unique start state Double circles mark any number of the states as accepting states For every state, for every symbol in ∑ , there is exactly one arrow labeled with that symbol going to another state (or back to the same state)

5. DFAs Define Languages Given any string over ∑ , a DFA can read the string and follow its state-to-state transitions At the end of the string, if it is in an accepting state, we say it accepts the string Otherwise it rejects The language defined by a DFA is the set of strings in ∑* that it accepts

6. The 5-Tuple Q is the set of states Drawn as circles in the diagram We often refer to individual states as qi The definition requires at least one: q0, the start state ∑ is the alphabet (that is, a finite set of symbols) A DFAM is a 5-tuple M = (Q, ∑, δ , q0, F), : where Qis the finite set of states∑ is the alphabet (that is, a finite set of symbols) δ (Q Q) is the transition function q0 Q is the start state F Q is the set of accepting states  

7. Regular Languages

8. Example

9. Regular Expressions

10. Regular Expressions A regular expression (RE) describes a language. It uses the three regular operations. These are called union/or, concatenation and star . Brackets ( and ) are used for grouping, just as in normal math.

11. Example An RE for the language of all binary strings of length at least 2 that begin and end in the same symbol . 0(0 + 1) ∗0 + 1(0 + 1) ∗1 Note precedence of regular operators: star always refers to smallest piece it can, or to largest piece it can.

12. Example Consider the regular expression ((0 + 1) ∗1 + ε) (00) ∗ 00 This RE is for the set of all binary strings that end with an even nonzero number of 0’s. Note that different language to: (0 + 1) ∗ (00) ∗ 00

13. Regular Operators for Languages If one forms RE by the or of REs R and S, then result is union of R and S. If one forms RE by the concatenation of REs R and S, then the result is all strings that can be formed by taking one string from R and one string from S and concatenating . If one forms RE by taking the star of RE R, then the result is all strings that can be formed by taking any number of strings from the language of R (possibly the same, possibly different), and concatenating.

14. Regular Operators Example If language L is {ma, pa} and language M is {be, bop}, then L +M is {ma, pa, be, bop}; LM is { mabe , mabop , pabe , pabop }; and L ∗ is { ε, ma, pa, mama, . . . , pamamapa , . . .}. Notation : If Σ is some alphabet, then Σ ∗ is the set of all strings using that alphabet.

15. Practice Give an RE for each of the following three languages: All binary strings with at least one All binary strings with at most one All binary strings starting and ending with

16. Solution (0 + 1) ∗0(0 + 1) ∗ 1 ∗ + 1 ∗01 ∗ 0(0 + 1) ∗0 + In each case several answers are possible.

17. Context-Free Grammar

18. 22 Informal Comments A context-free grammar is a notation for describing languages. It is more powerful than finite automata or RE’s, but still cannot define all possible languages. Useful for nested structures, e.g., parentheses in programming languages.

19. 23 Informal Comments – (2) Basic idea is to use “variables” to stand for sets of strings (i.e., languages). These variables are defined recursively, in terms of one another. Recursive rules (“productions”) involve only concatenation. Alternative rules for a variable allow union.

20. 24 Example : CFG for { 0 n 1 n | n > 1} Productions: S -> 01 S -> 0S1 Basis : 01 is in the language. Induction : if w is in the language, then so is 0w1.

21. 25 CFG Formalism Terminals = symbols of the alphabet of the language being defined. Variables = nonterminals = a finite set of other symbols, each of which represents a language. Start symbol = the variable whose language is the one being defined.

22. 26 Productions A production has the form variable -> string of variables and terminals . Convention : A, B, C,… are variables. a, b, c,… are terminals. …, X, Y, Z are either terminals or variables. …, w, x, y, z are strings of terminals only.  ,  ,  ,… are strings of terminals and/or variables.

23. 27 Example : Formal CFG Here is a formal CFG for { 0 n 1 n | n > 1}. Terminals = {0, 1}. Variables = {S}. Start symbol = S. Productions = S -> 01 S -> 0S1

24. 28 Derivations – Intuition We derive strings in the language of a CFG by starting with the start symbol, and repeatedly replacing some variable A by the right side of one of its productions. That is, the “productions for A” are those that have A on the left side of the ->.

25. 29 Derivations – Formalism We say  A  =>  if A ->  is a production. Example : S -> 01; S -> 0S1. S => 0S1 => 00S11 => 000111 .

26. 30 Iterated Derivation =>* means “zero or more derivation steps.” Basis :  =>*  for any string  . Induction : if  =>*  and  =>  , then  =>*  .

27. 31 Example : Iterated Derivation S -> 01; S -> 0S1. S => 0S1 => 00S11 => 000111. So S =>* S; S =>* 0S1; S =>* 00S11; S =>* 000111.