Alphabets , strings, languages and grammars

a Formal language Simple and basic Termes

1. Chapter One Alphabets , Strings, Languages and Grammars Prepared By Haftom B. 1

2. Prepared By Haftom B. 2

3. 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 Examples An alphabet is a finite set of symbols. S 1 = {a, b, c, d, …, z}: the set of letters in English S 2 = {0, 1, …, 9}: the set of (base 10) digits S 3 = {a, b, …, z, #}: the set of letters plus the special symbol # S 4 = {(, )}: the set of open and closed brackets Prepared By Haftom B. 3

4. Strings The empty string will be denoted by E Examples A string over alphabet S is a finite sequence of symbols in S. abfbz is a string over S 1 = {a, b, c, d, …, z} 9021 is a string over S 2 = {0, 1, …, 9} ab#bc is a string over S 3 = {a, b, …, z, #} ))()(() is a string over S 4 = {(, )} Prepared By Haftom B. 4

5. Cont.… We will use small alphabets: Strings 5 Prepared By Haftom B.

6. String Operations 6 1. Concatenation Prepared By Haftom B.

7. 7 2. Reverse Prepared By Haftom B.

8. 3. String Length Length: Examples: 8 Prepared By Haftom B.

9. Recursive Definition of Length For any letter: For any string : Example: 9 Prepared By Haftom B.

10. 4. Length of Concatenation Example : 10 Prepared By Haftom B.

11. Proof of Concatenation Length Claim: Proof: By induction on the length Induction basis : From definition of length: 11 Prepared By Haftom B.

12. Empty String A string with no letters: Observations: 12 Prepared By Haftom B.

13. Substring Substring of string: a subsequence of consecutive characters String Substring 13 Prepared By Haftom B.

14. Prefix and Suffix Given string Prefixes Suffixes 14 prefix suffix Prepared By Haftom B.

15. Another Operation Example: Definition: 15 Prepared By Haftom B.

16. The * Operation : the set of all possible strings from alphabet 16 Prepared By Haftom B.

17. 17 The + Operation : the set of all possible strings from alphabet except Prepared By Haftom B.

18. 1.2 Languages Languages can be used to describe problems with “yes/no” answers, for example: A language is a set of strings over an alphabet. L 1 = The set of all strings over S 1 that contain the substring “fool” L 2 = The set of all strings over S 2 that are divisible by 7 = {7, 14, 21, …} L 3 = The set of all strings of the form s#s where s is any string over {a, b, …, z} L 4 = The set of all strings over S 4 where every ( can be matched with a subsequent ) Prepared By Haftom B. 18

19. Cont.… A language is any subset of Example 1: Languages: 19 Prepared By Haftom B.

20. Example 2 An infinite language is aabbaa ? 20 Prepared By Haftom B.

21. 21 Note that: Sets Set size Set size String length Prepared By Haftom B.

22. 1.2.1 Operations on Languages The usual set operations Complement: 22 Prepared By Haftom B.

23. Reverse Definition: Examples: 23 Prepared By Haftom B.

24. Concatenation Definition: Example: 24 Prepared By Haftom B.

25. Another Operation Definition: Special case: 25 Prepared By Haftom B.

26. More Examples 26 Prepared By Haftom B.

27. Star-Closure (Kleene *) Definition: Example: 27 Prepared By Haftom B.

28. Positive Closure Definition: 28 Prepared By Haftom B.

29. Grammar Prepared By Haftom B. 29 A grammar is a mechanism used for describing languages. This is one of the most simple but yet powerful mechanism . The grammar for English tells us what are the words in it and the rules to construct sentences.

30. Formal definitions of a Grammar Prepared By Haftom B. 30 A grammar G is defined as a quadruple

31. Example Prepared By Haftom B. 31 Consider the grammar , where N = { S }, and P is the set of the following production rules .   Some terminal strings are generated by this grammar together with their derivation is given below

32. Cont.. Prepared By Haftom B. 32

33. Cont.… Prepared By Haftom B. 33 Example: Find a grammar for the language It is possible to find a grammar for L by modifying the previous grammar since we need to generate an extra b at the end of the string . We can do this by adding a production S Bb where the non-terminal B generates