language , grammar and automata

concept of language , grammar and automata in discreate mathematics

1. LANGUAGE , GRAMMAR & AUTOMATA Presentation by Elakkiya.S, Santhosh.B, Balamurugan.A,

2. Outline of the presentation Language Concatenation Properties of concatenation Regular expression Regular language Grammar Types of grammar Finite state machine Automata Automata and its types. Maths- seminar presentation- 07.06.2021 1

3. Language

4. Language: Definition: An alphabet is a non-empty finite set Σ of symbols. A string or word on the set Σ is a finite sequence of its elements (symbols) If Σ ={a,b} then the sequences u=abba and v=aabbb of letters are strings of Σ. The length of a string u is denoted by 丨u丨 is the number of symbols in the string If Σ={0,1,2} then u=01 v=212 and w=01212 are possible strings on A. the length of these strings is 丨u丨=2 丨v丨=3 丨w丨=5 The string consisting of no symbols or letters taken from an alphabet Σ, we define Σ⁰={λ}. 2

5. Operations on strings The basic operations for strings is concatenation operations. The concatenation of strings is a string formed by writing the letters (symbols) of first string followed by letters of second string Example : If u =ice and v= cream are the two strings of length 3 and 5 respectively.Then concatenation of u and v is uv=ice cream is the string of length 3+5=8. 3

6. Properties of concatenation If Σ is an alphabet and n is a non-negative integer then the power of ∑ is defined recursively as ∑1= ∑ and ∑n+1 = { ab:a∈A and b∈ ∑n} The concatenation Operation on an alphabet ∑ is associative , since for every u,v,w ∈ ∑* ... We have u(vw)=(uv)w. The concatenation operation is not commutative (unless 丨 ∑ 丨 =1)on an alphabet ∑ , since uv≠ vu for every u,v ∈ ∑* . 4

7. The empty string λ is an identity element for concatenation operation on an alphabet Σ that is λu=uλ=u for every u ∈ Σ* If u,v ∈ Σ* then we may write u=u1,u2,..........um and v=v1,V2,......vn. For m,n and u1,u2,...um;v1,v2..vn two string u,v are said equal. For every u,v,w ∈ ∑* we have wu= wv →u=v ( left cancellation) uw =vw →u=v ( right cancellation) For u, v ∈∑* we have │uv│= │u│+│v│ 5

8. Language Definition: For a given alphabet Σ , any subset of Σ* is called a language over Σ and is denoted by L. The subset Ф also called empty language. A string in a language L is called a sentence of Σ. 6

9. Operations on languages Operations on language : Let L1 and L2 be two languages over an alphabet Σ. Then the concatenation of L1 and L2 is denoted by L1L2 and is the language defined as L1L2={ab: a∈L1 and b∈L2} Examples : L1={a,ab,c} and L2={λ,b} L1L2={aλ,ab,abλ,abb,cλ,cb} ={a,ab,ab,abb,c,cb} 7

10. Problem : 8

11. Regular expression Regular expression such as ( ),*,U,λ that are used to develop expression for describing languages are called regular expressions. Thus the regular expression r over a non -empty alphabet Σ is a word which attaches the letters of Σ with the help of operation( ),*,U and λ. 9

12. Examples Each letter a∈Σ is a regular expression. Empty word λ and empty expression Φ are regular expression. If r is a regular expression then it 's closure expression r* is an regular expression. If r1,r2 are regular expression then r1+r2 is a regular expression. 10

13. Regular language The language L(r) represented by the regular expression r over an alphabet Σ is as follows; (1).If r =Φ then L(r)=Φ (2).If r=λ then L(λ)={λ} and L(())=ф empty set (3).If r=a for some a ∈ Σthen L(a)={a} (4).L(r*)=(L(r))* the kleene closure of L(r) (5).L(r1 v r2)= L(r1)UL(r2) union of two languages. 11

14. GRAMMAR

15. Grammar Definition A phrase structure grammar or simply a grammar G consists of four parts; 1. V 2.𝛴 3. S 4.P 12

16. V,Σ,S,P Definition V is a finite set,where elements are called variables. 𝛴 is a finite subset of V whose elements are called terminals. vn𝛴=ф S is special variable(non terminal symbol) in the set V called the start symbol that begins the generation of any sentence in the language. P is a finite set of whose elements are ordered pair (𝝰,𝜷) usually written as 𝜶⇾𝜷 where 𝝰 and𝛃 are string(word) on VUΣ and has at least one non-terminal on its left side elements of P are called productions or production rule. The grammar denoted by G=(v,Σ,s,p) 13

17. Language of grammar G Definition Let G=(V,Σ,S,P) be a grammar then the language L(G)generated by G is the set of all strings of terminals which are derivable from the starting state S. That is L(G)={w ∈ Σ*,s*⇒w} The elements of L(G) are usually called sentences. 14

18. p roblem (1) Find the language L(G) generated by the grammar with v={S,A,B},𝛴={a,b} and production p ={s→aB, B→b, B→bA , A→a,B}. Solution; S→aB →a bA →abaB →ababA →ababaB →ababab L(G)={(ab)ｎ=ababab…….ab:nƐN}. 15

19. Problem(2) Find the language L(G) generated by the grammar with V={s,a},Σ={a,b,c} and production p={S→asb,aS→Aa,Aab→c}. Solution; S →asb S→asb S→a asb b S→a asb b S→aa asb bb S→a Aabb S→aa Aa bbb S→acb S→aa c bb L(G)={an c bn : n≥1} 16

20. TYPES OF GRA MMAR

21. TYPES OF GRAMMAR Type 0 (OR) Phrase Structure Grammar Type 1 (OR) Context sensitive Grammar Type 2 (OR) Context Free Grammar Type 3 (OR) Regular Grammar 17

22. Type 0 (or) Phase Structure Grammar A Grammar G with no restriction on its productions is called A Type 0 Grammar 18

23. Type 1 (or)Context Sensitive Grammar A Grammar G said to be of type 1 if every production is of the form ∝→ß where 丨∝丨≤丨β丨or of the form ∝→λ. Here λ is the null string and ∝ , β are arbitrary string on v. 19

24. Type 2 (or)Context Free Grammar A Grammar G is said to be of type 2 if every production is of the form A→β. Where the left hand side string is always a single non terminal symbol. 20

25. Type 3 (or) Regular Grammar A Grammar G is said to be of type 3 if every production is of the form A→∝ (or) A→aB. Where the left hand side string is always a single non terminal symbol and the right hand side string is either terminal symbol (or) a terminal symbol Followed by a non-terminal symbol or of the form S→λ. 21

26. Problems: Determine the type of grammar G in the following: a)p = { S→aA, A→aAB, B→b , A→a } b)p = { S→ b, S→aA, A→b , A→bB, A→aA, B→a, B→aB } c)p = { S→aAB, AB→a, A→b, B→AB } d)p = { s→b, S→aA, A→b, A→aA, A→bB, B→a, B→aB } Soln: a)Type 2 (OR) Context Free Grammar. b) Type 3 (OR) Regular Grammar. c) Type 0 (OR) Phrase Structure Grammar. d) Type 1 (OR) Context sensitive Grammar. 22

27. Finite state machine

28. Finite state machine A finite state machine M consists of six parts: Σ, finite set of input alphabet symbols ai(i=1,2...n) with or without subscripts are input symbols. S,a finite set of internal state . The state S₀ is the initial state, O is a finite set of the output alphabet that is O={x,y,z}. f,a transition (or next state)function or mapping from s *Σ into S. that is f: s *Σ→S g,a output function from S *Σ into O. that is g:S *Σ→0 Such a machine is written as M={Σ,S,S₀ ,o,f,g} 23

29. The Features of Finite State machine At any given time,the machine can be only one of finite number of states.This States are called the internal States of the machine. The machine accepts as input Only a finite number of symbols the finite set of all possible inputs constitute the input alphabet for the machine. An output and a next state are determined by each combination of Inputs and internal states.The finite set of all possible outputs constitute the output alphabet for the machine. We assume that the machine has an internal clock,an the sequential processing are synchronised by separate and distinct clock pulses. 24

30. State Table and State Diagram of a Finite State machine: A Finite state machine M can be represented in compact form by means of A state-table also called transition table of M A labelled directed graph called the state diagram or transition diagram of M. The state table combines the state function ‘f’ and the output function ‘g’ for all pairs of state and inputs The first column of the table list the (present )state for the machine . Entries in the second row are the elements of the input alphabet Σ listed once under f and then again under g. The six numbers in the last two columns (and last three rows)are elements of the output alphabets O. 25

31. State transition table and state diagram 26

32. Problem(1) Let m be the finite state machine with state Table Given the following page. Find the input set Σ ,the state set S,the output set O and the initial state of M. Draw the state diagram of M. Find the output string of the input string 01001. 27

33. Solution (A).Input set Σ ={0,1} State set s ={S0,S1,S2,S3} Output set 0={0,1} Initial state=S0 28

34. Finite state automata

35. Finite state automata: ite state automaton is a special type of finite state machine in which there is no output , and some of its states are distinguished as accepting states. There are two types of automati A fin on Deterministic finite state automation Non-deterministic finite state automation 29

36. Deterministic Finite St ate A utomaton (DFA) A deterministic finite state automaton or simply an automaton M consists of five parts: A finite non empty set 𝚺 of inputs, called alphabets A finite non empty set s of (internal) state. A next state function ( also called transition function) f from s* 𝚺 into s . This function or mapping describes the change of states during the transition. It is usually represented by a state transition table or a state transition diagram. A subset F of set S of accepting (final) states. An initial state s₀𝟄S. Such a finite state automaton is denoted by M=( 𝚺,S,S𝜊,f). 30

37. State Transition Diagram A typical state transition diagram is shown. This diagram is a finite directed labelled graph so that Each vertex (node) represents a state, The directed edges are represented by arrows and indicate the transition from state si to state sj.The final state is represented by double circle. The initial state s₀ is represented by a circle with an arrow pointing towards 31

38. Definition A string w is said to be accepting by a finite automaton M provided. There exists a path which originates from some initial state ,goes along the arrows and terminates at some final state ,and The path value obtained by concatenation of all edge labels of the path is equal to w Trap state A state from which a dfa can never come out is called a trap state. 32

39. problem: Consider the transition diagram shown Find its state Find its input symbols Find its initial state Find its accepting states Find f(s2,1) Write its next state table 33

40. Solution State S={s𝜊,s1,s2,s3} Input symbol 𝚺={0,1} Initial state=s𝜊 Accepting states=S𝜊 f(s2,1)=s3 Next state table ------------------------------------------- State f(input) 0 1 S𝜊 S2 S1 S1 S3 S𝜊 S2 S𝜊 S3 S3 S1 S2 34

41. Non Deterministic Finite State Automaton A non-deterministic finite state automaton (nfa) allows zero,one or more transitions from a state on the same input symbol. A non-deterministic finite state automaton m consists of five parts: A finite non empty set 𝚺 of input symbols. A finite non empty set s of state. A next state function ( or mapping) f from s* 𝚺 into p(s) , which is the power set of S. that is the set of all subsets of S which are v equal to 2 power s A subset F of set S of accepting (final) states. An initial state s₀𝟄S. Such a finite state automaton is denoted by M=( 𝚺,S,S𝜊,f). 35

42. problem For a non deterministic finite state automaton shown..find Initial state State set Input set State table defining the next state function s olution: Initial state=S𝜊 State set={S𝜊,S1,S2} Input set ={0,1} Next state func State f S𝜊 {S1,S2} ф S1 ф {S𝜊,S2} S2 ф S𝜊 36