Introduction to Alphabets, Strings, and Languages
Alphabets, strings, and languages are fundamental concepts in computer science and linguistics. Alphabets consist of finite sets of symbols, strings are sequences of symbols, and languages are sets of strings over an alphabet. Understanding these concepts is essential for studying topics like deterministic finite automata. Explore the definitions and examples provided to grasp the basics of these foundational elements.
Uploaded on Feb 26, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Alphabets and strings A common way to talk about words, number, pairs of words, etc. is by representing them as strings To define strings, we start with an alphabet An alphabet is a finite set of symbols. Examples 1= {a, b, c, d, , z}: the set of letters in English 2= {0, 1, , 9}: the set of (base 10) digits 3= {a, b, , z, #}: the set of letters plus the special symbol # 4 = {(, )}: the set of open and closed brackets
Strings A string over alphabet is a finite sequence of symbols in . The empty string will be denoted by Examples abfbz is a string over 1= {a, b, c, d, , z} 9021 is a string over 2= {0, 1, , 9} ab#bc is a string over 3= {a, b, , z, #} ))()(() is a string over 4 = {(, )}
Languages A language is a set of strings over an alphabet. Languages can be used to describe problems with yes/no answers, for example: The set of all strings over 1 that contain the substring fool The set of all strings over 2 that are divisible by 7 {7, 14, 21, } The set of all strings of the form s#s where s is any string over {a, b, , z} The set of all strings over 4 where every ( can be matched with a subsequent ) L1 = L2 = = L3 = L4 =
Deterministic Finite Automata A deterministic finite automaton (DFA) is a 5-tuple (Q, , , q0, F) where Q is a finite set of states is an alphabet : Q Q is a transition function q0 Q is the initial state F Q is a set of accepting states (or final states). In diagrams, the accepting states is be denoted by double loops (or plus)
Deterministic Finite Automata Definition: A Finite automaton (FA), is a collection of the followings: 1) Finite number of states, having one initial and some (maybe none) final states. 2) Finite set of input letters ( ) from which input strings are formed. 3) Finite set of transitions i.e. for each state and for each input letter there is a transition showing how to move from one state to another.
Example 0 1 0,1 1 0 q0 q1 q2 transition function alphabet = {0, 1} start stateQ = {q0, q1, q2} initial stateq0 accepting statesF = {q0, q1} inputs 0 q0 q2 q2 1 q1 q1 q0 q1 q2 states q2
Language of a DFA The language of a DFA (Q, , , q0, F) is the set of all strings over that, starting from q0 and following the transitions as the string is read left to right, will reach some accepting state. f on M: off f Language of M is {f, fff, fffff, } = {f n: nis odd}
Language of a DFA f on off f There are states off and on, the automaton starts in off and tries to reach the good state on What sequences of fs lead to the good state? Answer: {f, fff, fffff, } = {f n: nis odd} This is an example of a deterministic finite automaton over alphabet {f}
Input Tape b a a q0 +q1 b
Example 1 Construct a DFA that accepts the language ( = {0, 1} ) L = {010, 1} Answer 1 0 q0 q01 q010 0 0 1 q 0, 1 1 0, 1 q1 qdie 0, 1
Example 2: (a+b)+ a,b a,b +
Example 3: (a + b)* a,b a,b + a,b
Example 4: a(a+b)* a,b b a,b a +
Example 7: b(a + b)* a,b b + a,b a
Example 8: (a+b)*a b a a + a b a + a b b b
Example 9: a (a + b)* + a,b a + a,b b
Example 10: a(a+b)*a + b(a+b)*b b a a + a b a b b b + a
Example 11: (a+b) + a(a+b)*a + b(a+b)*b a a b a b + + a b b b a b b a + + a
Example 12: a(a+b)*b + b(a+b)*a b a b + a a a b a b + b
Example 13: FA that does not accept any string a,b a,b + a,b a,b a,b
Example 14: (a+b)* aa (a+b)* a,b b a a + b
Example 15: (0+1)* (00 + 11) (0+1)* 0 0 0,1 0 1 + 1 1
Example 16: (a+b)* (aaa + bbb) (a+b)* a a a b a,b b a + a b b b
Example 17: (aa+bb+(ab+ba)(aa+bb)*(ab+ba))* b b a a a a b b
a,b Example 18 a +b+ab+bb OR +b( +a+b) a,b a b + b b + + a,b a Dead States, Waste Baskets or Davey John Lockers, as the moment one enters these states there is no way to leave it a,b
a,b Example 19 a,b a b a a a b b b + + aa + bab + aabb + bbba b b a + OR a aa ( + bb) + b (ab + bba) a b a,b a b a,b + a,b
Example 20: (a+b)*(ab+ba) a b + a b a a b b b a +
Example 21: (a+b)*(ab+ba) a aa a b a b a a ab b a ba b a b a b b b Introduction to Languages and Theory of Computation, by J. C. Martin bb
Example 22 a aa + a + b + (a+b)*(ab+ba+bb) a b a b a a ab b a ba b a b a b b b bb
Example NFA INPUT: 010110
Transition Graphs A transition graph (TG) is a collection of three things: 1. A finite set of states at least one of which is designated as the start state (-) and some (maybe none) of which are designated as final states (+). 2. An alphabet ( ) of possible input letters from which input strings are formed. 3. An finite set of transitions that show how to go from one state to another based on reading specified substrings of input letters(possibly even the null string ( ).
Example 2: (a+b)* aa (a+b)* b,a b,a aa - +
Example 5: (a+b)* (aa + bb) (a+b)* a a,b a,b a + b b a,b a,b aa,bb - +
