Regular Languages and Grammars PDF

Regular languages and Regular Grammars Prof. Vaibhavi Patel, Assistant Professor Computer Science and Engineering  Topic Regular Expressions Link to RE  Topic RE and FA- inter conversion RE FA  Topic Properties of regular languages Propertie...

Regular languages and Regular Grammars Prof. Vaibhavi Patel, Assistant Professor Computer Science and Engineering  Topic Regular Expressions Link to RE  Topic RE and FA- inter conversion RE FA  Topic Properties of regular languages Properties of regular languages Regular languages have two important kinds of properties: 1.Closure properties. 2.Decision properties.  Sub-Topic Closure properties Properties of regular languages: Closure properties Closure properties on regular languages are defined as certain operations on regular language which are guaranteed to produce regular language. Closure refers to some operation on a language, resulting in a new language that is of same “type” as originally operated on i.e., regular. Properties of regular languages: Closure properties Regular languages are closed under following operations. Let L and M be regular languages. Then the following languages are all regular: – Union: L ∪ M – Intersection: L ∩ M – Complement: L – Difference: L - M or M - L – Concatenation: L. M – Reversal: LR – Kleen Closure: L∗ – Positive Closure: L+ Closure properties: Closure under Complementation If 𝐿 ⊆ Σ∗ , then the complement of 𝐿, denoted 𝐿, is Σ∗ − 𝐿. Theorem: If 𝐿 is a regular language over Σ, then 𝐿 is also a regular language. Proof: – Construct a DFA for 𝐿 – This can be transformed into a DFA for 𝐿 by making all accepting states non-accepting and vice versa. Closure properties: Closure under Reversal The reversal of 𝐿, written 𝐿𝑅 is {𝑥 | 𝑥𝑅 ∈ 𝐿} The reversal of a language L, is the language consisting of the reversals of all its strings Example: L = {001, 10, 111} Theorem: If 𝐿 is regular, then so is 𝐿𝑅. LR = {100, 01, 111} Proof: – Start with a FA for 𝐿. – Reverse all of the transitions in the FA – Make the FA’s start state the only accepting state. – Create a new start state with 𝜀-transitions to all of the original accepting states.  Sub-Topic Decision properties Properties of regular languages : Decision properties A property is a yes/no question about languages. Some examples: ❖Is 𝐿 empty? ❖Is 𝐿 finite? ❖Are 𝐿1 and 𝐿2 equivalent? A property is a decision property for regular languages if an algorithm exists that can answer the question (for regular languages). Properties of regular languages : Decision properties Following are the decision properties for FA: 1.Emptiness 2.Finiteness 3.Equivalence 4.Membership Decision properties: Emptiness and Non-emptiness Does the language contain any string at all? Algorithm: – Select the state that cannot be reached from the initial states & delete them (remove unreachable states). – If the resulting machine contains at least one final states, so then the finite automata accepts the non-empty language. – if the resulting machine is free from final state, then finite automata accepts empty language. Decision properties: Finiteness and Infiniteness Is the language accepted by FA is finite or infinite? Algorithm: – Select the state that cannot be reached from the initial state & delete them (remove unreachable states). – Select the state from which we cannot reach the final state & delete them (remove dead states). – If the resulting machine contains loops or cycles then the finite automata accepts infinite language. – If the resulting machine do not contain loops or cycles then the finite automata accepts finite language. Decision properties: Equivalence We want an algorithm that takes two languages, 𝐿1 and 𝐿2, and determines if they are the same? Algorithm: – Convert 𝐿1 and 𝐿2 to DFAs. – Convert 𝐿1 and 𝐿2 to minimal DFAs. – Determine if the minimal DFAs are the same. Decision properties: Membership Membership is a property to verify an arbitrary string is accepted by a finite automaton or not? i.e. it is a member of the language or not? Let M is a finite automata that accepts some strings over an alphabet, and let ‘w’ be any string defined over the alphabet, – if there exist a transition path in M, which starts at initial state & ends in anyone of the final state, then string ‘w’ is a member of M, otherwise ‘w’ is not a member of M.  Topic Regular set  Regular set Any set that represents the value of the Regular Expression is called a Regular Set.  Properties of Regular Sets Property 1. The union of two regular set is regular. Property 2. The intersection of two regular set is regular. Property 3. The complement of a regular set is regular. Property 4. The difference of two regular set is regular. Property 5. The reversal of a regular set is regular. Property 6. The closure of a regular set is regular. Property 7. The concatenation of two regular sets is regular. Every subset of regular language is not regular  Topic Regular Grammars  Grammars Def: Grammar is set of rules used to derive strings of the language. or A grammar G can be formally written as a 4-tuple (V, T, P, S) where − N or V is a set of variables or non-terminal symbols. T or ∑ is a set of Terminal symbols. Alphabets of language. P is Production rules for Terminals and Non-terminals. S is a special variable called the Start symbol, S ∈ V P is set of production rules; has the form α → β, where α and β are strings on V ∪ ∑ and least one symbol of α belongs to V  Grammars-Example ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } ) – Here, S and A are Non-terminal symbols. a and b are Terminal symbols. ε is an empty string. S is the Start symbol, S ∈ N Production P : S → aAb, aA → aaAb, A → ε  Derivations from a Grammar Strings may be derived using the productions in a grammar. For Example Let us consider the grammar − G = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } ) Derivation of the string: ‘aaabbb’ S ⇒ aAb using production S → aAb ⇒ aaAbb using production aA → aAb ⇒ aaaAbbb using production aA → aAb ⇒ aaabbb using production A → ε Derivations from a Grammar  Grammar: Regular grammars The set of all strings that can be derived from a grammar is said to be the language generated from that grammar. Regular Grammar generates Regular language which is accepted by Finite automata. Regular Grammar also known as Type 3 grammar. Grammar: Regular grammars RLG (right linear grammar): LLG (Left linear grammar): V -> αV / β V -> Vα / β Regular grammars: example Regular grammars: example  Topic Equivalence with finite automata  FA -> RLG Step1: Initial state is start symbol Step 2: If 𝛿(A,a)=B is a transition then A->aB is a production, write production rules for all the transitions Step 3: If B is a final state then add B-> ε ; because that's is required to end the derivation FA -> RLG  RLG ->FA Step1: Start from the first production Step 2:Start State: It will be the first production's state Step 3: And then for every left alphabet go to SYMBOL followed by it Step 4: Final State: Take those states which end up with input alphabets. RLG ->FA Example: RLG ->FA Example:  FA -> LLG Step1: Interchange initial and final state Step 2: Change the direction of the edges Step 3: Obtain RLG step 4: Reverse the RHS of every production  FA -> LLG Why?  FA -> LLG Example:  FA -> LLG Example: LLG ->FA LLG ->FA Example:  Topic Equivalence with RE Thank You