Regular Languages and their Properties Prof. (Dr.) K.R. Chowdhary Former Professor & Head, Department of Computer Sc. & Engineering MBM Engineering College, Jodhpur kr chowdhary TOC 1/ 14 K.R. Chowdhary Theory of Computation Automata, Formal Languages, Computation and Complexity Focuses on pedagogy in its writing, that represents a refreshing approach Ensures comprehensive and enjoyable learning Undergone a rigorous classroom testing ©2025 Get 20% off with this code: SPRAUT Available on Springer Nature Link Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books & eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks, encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply. Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers, book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us. Promotions do not work in combination with other discounts or gift cards. link.springer.com/book/ 9789819762347 Introduction to Regular languages There is a cycle: for regular expression there is corresponding regular language, for reg. language there is a corresponding NFA, for NFA there is a corresponding DFA, and for that there is a corresponding regex. It indicates that all these have same capabilities. We know that regular expressions are closed on ∪, ◦, and ∗. Do these properties also apply to Reg, languages? kr chowdhary TOC 2/ 14 Regular languages are closed on ∪, ◦, and ∗ The approach for this is: If after performing these operations on reg. languages, if they are still accepted by FA, then they (reg. languages) are closed. This is because, the FA recognize regular languages. Thus, the proof reduces only to: find corresponding FA for these closure properties. Theorem Regular languages are closed on Union. Proof. Assume that M1 = (Q1 , Σ1 , δ1 , s1 , F1 ) and M2 = (Q2 , Σ2 , δ2 , s2 , F2 ) are two FA recognizing the regular languages L1 = L(M1 ) and L2 = L(M2 ). Let L(M) = L(M1 ) ∪ L(M2 ) is the language recognized by a union automaton, such that, L(M) = {w |w = x ∪ y , x ∈ L1 , y ∈ L2 }. That is, M accepts w iff M1 accepts x or M2 accepts y . kr chowdhary TOC 3/ 14 Regular languages Theorem Proof. Closed on Union: Let the automata M which accepts L1 ∪ L2 is as shown below. If w = x, the FA M non-deterministically decides a ε-transition from new state s to s1 , and then there are transitions in M1 , and when f1 ∈ F1 is encountered there is a ε−transition from f1 to f . Similar phenomena occurs for M2 when w = y . The resultant FA M = (Q, Σ, δ , s, F ) is given as: Q = Q1 ∪ Q2 ∪ {s, f }, Σ = Σ1 ∪ Σ2 ∪ {ε}, start state=s, final state=f , and δ is given in next slide. kr chowdhary TOC 4/ 14 Regular languages theorem Proof. Closed on Union contd.: The δ δ (q, a) = δ1 (q, a), if q ∈ Q1 and a ∈ Σ1 δ (q, a) = δ2 (q, a), if q ∈ Q2 and a ∈ Σ2 δ (q, a) = {s1 , s2 }, if a = ε and q = s δ (q, a) = δ (q, a) = f , if q ∈ F1 ∪ F2 and a ∈ ε hence L = L(M) = {x ∪ y | x ∈ Σ∗1 , and y ∈ Σ∗2 }. kr chowdhary TOC 5/ 14 Regular languages theorem Theorem Regular languages are closed on the operation of concatenation. Proof. Let L = L(M1 ) ◦ L(M2 ) = {w = x ◦ y | x ∈ L(M1 ), y ∈ L(M2 )}. Here, M1 recognizes x and reaches to its final state, then there is a ε-transition from f1 ∈ F1 to s2 , then M2 recognizes y . M is defined in terms of M1 and M2 as: Q = Q1 ∪ Q2 , Σ = Σ1 ∪ Σ2 ∪ {ε}, s = s1 , f = f2 and δ is: δ (q, a) = δ1 (q, a), q ∈ Q1 , a ∈ Σ1 , δ (q, a) = {s2 }, q ∈ F1 , a = ε δ (q, a) = δ2 (q, a), q ∈ Q2 , a ∈ Σ2 . kr chowdhary TOC 6/ 14 Regular languages theorem Theorem Regular languages are closed on the operation of kleene-star. Proof. This is extension of concatenation, i.e., the input x ∈ L(M1 ) is pumped zero or more number of times. L = L(M) = (L(M1 )∗ ) = L∗1 = {w = x ∗ | x ∈ L1 }. The formal definition of M = (Q, Σ, δ , s, F ) is: Q = Q1 ∪ {s, f }, Σ = Σ1 ∪ {ε}, start state=s, final state=f , and δ is: kr chowdhary δ (q, a) = {s1 , f }, if q = s, a = ε, δ (q, a) = δ1 (q, a), if q ∈ Q1 , a ∈ Σ1 , δ (q, a) = {s1 ∪ f }, if q ∈ Q1 , a = ε This proves the theorem. TOC 7/ 14 Construction of FA for a given Regex Example Given the regex r = (ab + aba)∗ , we can find the FA as follows: Systematically apply the theorem discussed above to construct the FA using elementary steps. 1. Construct the NFA for regex r1 = ab, 2. Construct NFA for r2 = aba, 3. Construct NFA for r3 = r1 + r2 = ab + aba, 4. Finally, construct NFA for r3∗ = (r1 + r2 )∗ = (ab + aba)∗ kr chowdhary TOC 8/ 14 FA to Regex: State removal method Lemma A language is regular then it can be described by a regex. Proof. 1 Because L is regular, it can be represented by a DFA. 2 Convert the DFA into equivalent regex. 3 First convert DFA into GNFA (Generalized NFA) then convert GNFA into regex. This proves the lemma. Definition (GNFA.) A GNFA G reads blocks of symbols rather than single symbol at a time, has single start state and single final state. If GNFA is G = (Q, Σ, ρ, q0 , qf ), then ρ : Q − {q0 } × Q − {qf } → RΣ , RΣ is set of all regular expressions over alphabet Σ. kr chowdhary TOC 9/ 14 FA to Regex: State removal method 1 DFA-to-GNFA: add new start state (qstart ) with ε−transition to original start state q0 2 add new end state with ε−transition from each of the original final state. 3 If original transition arrow has multiple labels, we replace these with a new arrow whose label is regular expression formed by the union of the labels. 4 we iteratively remove one state in GNFA, such that new GNFA obtained will recognize the same language. 5 When number of states in GNFA are two, we have obtained the regex for the given DFA. kr chowdhary TOC 10/ 14 FA to Regex: State removal method Example The diagram below shows state removal and gives regex for a FA. kr chowdhary TOC 11/ 14 FA to Regex Brozozowski’s method This method generates regex by generating sequence of symbols (or equivalently, scanning the sequence of symbols). Suppose we want to find the regular expression for the FA given below. q = 0q + (1p + ε); ε symbols indicates that when input is accepted, no transition is required. So, q = 0∗ (1p + ε); by Arden’s theorem: X = X 1 + Y = X ∗ Y , so q = 0∗ 1p + 0∗ (ε) = 0∗ 1p + 0∗ p = 0p + 1q Starting from each state we we write a equation showing the generating of sequence of state and edge labels. Finally, after doing substitutions, we keep the equation of start state, without any variables(i.e., other state symbols). p = 0p + 1q kr chowdhary = 0p + 1(0∗ 1p + 0∗ ) = 0p + 10∗ 1p + 10∗ = (0 + 10∗ 1)∗ (10∗ ); by Arden’s rule. Hence, the required regex is (0 + 10∗ 1)∗ (10∗ ). TOC 12/ 14 Kleene’s theorem Theorem A language is regular iff it is accepted by FA. Proof. The proof has two parts: 1. If the language is regular then it is accepted by FA, and 2. If a language is accepted by FA then it is regular. Part 1: By definition of regularity, following are regular: φ , {a1 , a2 , . . . , an }, {ai } ∪ {aj }, {ai } ◦ {aj }, ai∗ . The diagrams shown below are of FA recognizing the first two. We have already proved that FA exists for the following regular languages: kr chowdhary {ai } ∪ {aj }, {ai } ◦ {aj }, ai∗ . Part 2: Using the method of state reduction (converting to GNFA) and Brozozowki methods we have proved that there exists regex for every FA. Hence, the complete proof. TOC 13/ 14 Bibliography Chowdhary, K.R. (2025). Regular Languages. In: Theory of Computation. Springer, Singapore. https://doi.org/10.1007/978-981-97-6234-7_5 kr chowdhary TOC 14/ 14