Chapter 09. Language Properties

Models of Language Generation: Grammars

1

9. Properties of the Formal Languages Every language has structural properties. For example, every string in the language {anbn | n > 0 } has a’s followed by b’s, and their numbers are same. Since, in general, it is impractical to define a language in terms of set properties, we use grammars. However, it is very difficult problem to figure out the structure of the language generated by a grammar G. In fact, it has been shown that for a given grammar G, the decision problem of whether L(G) = Σ * or not is unsolvable, except for regular and deterministic context-free grammars, where Σ is the set of terminal symbols of G. Given two grammars G1 and G2, it is also proven that the problem of deciding whether or not L(G1) = L(G2) is unsolvable, except for the cases where both grammars are regular or deterministic context-free grammars. In fact, the problem remains open for the grammars whose languages can be recognized by a DPDA. We classify formal grammars (and their languages) into type 0 (phrase structured), type 1 (context-sensitive), type 2 (context-free), and type 3 (regular) according to the format of the rules. An interesting question is; Are there any properties that the class of languages commonly exhibit? In this chapter, we answer this question for regular and context-free languages by examining what happens under the various set operations. 9.1 Properties of regular languages 240 Union, Concatenation, Kleene star, Reverse, Complement, Intersection, Set subtraction 9.2 Properties of context-free languages 245 Union, Concatenation, Kleene star, Reverse, Complement Rumination 248 Exercises 251

2

Properties of Languages

9.1 Properties of regular languages Theorem 9.1 Let L1 and L2 be regular languages. The result of each of the following set operations is also regular, i.e., regular languages are closed under each of the following set operations. (1) L1 ∪ L2 (union) (2) L1L2 (product) (3) L1∗ (Kleene star) (4) L1R (reversal) (5) L1 (complement) (6) L1 ∩ L2 (intersection) (7) L1 - L2 (set subtraction)

3

Properties of regular languages

Properties of Languages

Proof. Let G1 and G2 be regular grammars, respectively, generating the languages L1 and L2, and let M1 and M2 be DFA, respectively, recognizing L1 and L2. (Recall that every regular language is recognized by a DFA.) Let r1 and r2 be regular expressions, respectively, denoting L1 and L2. (Recall that every language denoted by a regular expression is regular.) (1) (union). The regular expression r1+ r2 denotes L1 ∪ L2. Since every language expressible by a regular expression is regular, L1 ∪ L2 is regular. (2) (product). The regular expression r1r2 denotes L1L2. Hence, L1L2 is regular. (3) (Kleene star). The regular expression (r1)* denotes L1∗. Hence, L1∗ is regular.

4

Properties of Languages

Properties of regular languages

(4) (reverse). Using DFA M1, which recognizes L1, we can construct an FA that recognizes L1R. (The following example shows the procedure.) This implies that L1R is also regular. Add a new accepting state, and link an ε -transition from every accepting state to this new accepting state. (This FA recognizes the same language.)

a

a a start

b

a a

b

ε

a start

a a

start

ε a

a

b

b

A N I

b

ε a

b

b

b

ε a

b

Let the state added be the start state, the old start state be the only accepting state, and reverse all the edges. This NFA recognizes the reverse of the language recognized by the original FA. 5

Properties of Languages

Properties of regular languages

(5) (complement). Using DFA M1, which recognizes L1, we can construct a DFA that recognizes the complement of L1, as the following example shows. (Recall that for convenience, we do not show the dead state and the transitions entering to it.)

a

Show the dead state and all the transitions entering it.

a a

b

start

b a

b

b

a,b

a,b

start

b a

b a

a

start b

a

b b

a Change the accepting states to non-accepting states, and non-accepting states to accepting states.

a

a

b b A N I

6

Properties of regular languages

Properties of Languages

(6) (intersection). By the equality shown below and the properties (1) and (5) (i.e., the closure under union and complementation), L1 ∩ L2 is also regular.

L1 ∩ L2 = L1 ∩ L2 = L1 ∪ L2 (7) (set subtraction). Since L1 - L2 = L1 ∩ L2 , by the closure properties (5) (closure under complementation) and (6) (closure under intersection), the language L1 - L2 is also regular. Pressure

Break Time

Pressure is part of life: adapt to it and use it! I don’t do without pressure. A physical therapist said, “Get in tune with your body.” But if I listened to my body, I’d stay in bed all morning.” - Stan Pottinger -

7

Properties of Languages

9.2 Properties of Context-free Languages The properties of context-free languages are a little different from those of regular languages. As the following theorem shows, they are not closed under intersection and complementation. Theorem 9.2 Context-free languages are closed under union, product, Kleene star, and reversal. They are not closed under intersection and complementation. Proof: For the proof, we will use context-free grammars exclusively. (We may use PDA’s, but in general the proofs become somewhat unwieldy.) Let L1 be L2 two arbitrary context-free languages that are, respectively, generated by context-free grammars G1 = (N1, T1, P1, S1 ) and G2 = (N2, T2 , P2, S2 ). Assume that N1 ∩ N2 = φ , i.e., the two grammars use different nonterminal symbols. Otherwise, we can simply modify one of the grammars and let them meet this condition without changing the language. Now, we prove the theorem. (1) (union). We construct a context-free grammar G by merging all the rules from G1 and G2, and then add a new start symbol S and the rules S → S1 | S2. Grammar G generates L1 ∪ L2 . 8

Properties of Languages

Properties of CFL

(2) (product). We construct a context-free grammar G by merging all the rules of G1 and G2, and then adding new start symbol S and the rule S→S1S2. This grammar generates the language L1L2 . (3) (Kleene star). We modify G1 by introducing a new start symbol S and adding the rule S → S1S | ε . This modified G1 generates the language (L1)*. (4) (reversal). To make a context-free grammar that generates (L1)R , we reverse the right side of every rule in G1. Now we prove that context-fee languages are not closed under intersection and complementation. For this proof, it is enough to show a counter example. (5) (intersection). We can show that languages L1 and L2 shown below are context-fee by either constructing a PDA or a CFG. However, language L3 is not context-free, which we will prove in Chapter 12. L1 = {a i b i c j | i, j ≥ 0 },

L2 = {a k b nc n | k, n ≥ 0 }

L3 = L1 ∩ L2 = {a i b i c i | i ≥ 0 } 9

Properties of CFL

Properties of Languages

(6) (complement). To the contrary, suppose that the context-free languages are closed under complementation. Then both L1 and L2 are context-free. We will use the following property; L 1 ∩ L 2 = L1 ∩ L 2 = L 1 ∪ L 2 By property (1), the union L1 ∪ L2 is also context-free. It follows that L1 ∪ L2 = L1 ∩ L2 is context-free. This contradicts to the proven fact that context-free languages are not closed under intersection. Break Time Enjoy Sharing A young man saw an elderly couple sitting down to lunch at McDonald's. He noticed that they had ordered one meal, and an extra drink cup. As he watched, the gentleman artfully divided the hamburger in half, then counted out the fries, one for him, one for her, until each had half of them. Then he poured half of the soft drink into the extra cup and set that in front of his wife. The old man then began to eat, and his wife sat watching, with her hands folded in her lap. The young man decided to ask if they would allow him to purchase another meal for them so that they didn't have to split theirs. The old gentleman said," Oh no. We've been married 50 years, and everything has always been and will always be shared, 50/50." The young man then asked the wife if she was going to eat, and she replied, "It's his turn with the teeth.“ - Fred & Wanda -

10

Properties of Languages

Rumination(1) : language properties

• Property (4) of regular languages says that if L is regular, so is L . Let G be a regular grammar whose language is L. As R

the following example shows, if we reverse the right side of every rule of G, then the resulting grammar G’ generates the reverse of L(G), which is also regular according to the closure property of regular languages under reversal. G:

S → abA | ac

A → bS | a

G’:

S → Aba | ca

A → Sb | a

Recall that every rule of a regular grammar has the restricted form of either A → xB or A → y, where A, B ∈ VN and x, y ∈ (VT )*, where VN and VT are, respectively, the sets of nonterminals and terminals. In other words, at the right side of every rule, at most one nonterminal symbol can appear, positioned at the right end, if any. We call such grammars rightlinear. In contrast, the left-linear grammars are the ones whose rules have the restricted form of either A → Bx or A → y. Both right-linear grammars and left-linear grammars generate the same class of regular languages. We can prove this by showing that (1) every language generated by a left-linear grammar is regular, and (2) every regular language can be generated by a left-linear grammar as follows. Proof (1). Let G be a left-linear grammar. Construct a right-linear grammar G’ by reversing the right side of every rule of G. Grammar G’ generates the reverse of L(G), i.e., L(G) = (L(G’))R. Since G’ is a right-linear, L(G’) is regular. Since the reverse of every regular language is also regular, L(G) is regular. Proof (2). We argue with the same logic. Let L be a regular language. By the closure property under reversal, LR is regular. Let G be a right-linear grammar which generates LR . Construct a left-linear grammar G’ by reversing the right side of every rule of G. Grammar G’ generates L.

11

Properties of Languages

Rumination (1): language properties

• We used DFA to prove that the complement of a regular language is regular. The proof does not work with NFA. Here we show an example. The language recognized by the NFA in figure (a) is {a, aa}, whose member cannot be in its complement. However, the NFA in figure (c) accepts both a and aa.

a

a start

start

a (a) a

a

start

Convert the states of accepting and non-accepting

a a (c)

a

Add the dead state

a

a a

a

a (b)

a

a

• For the proof of the closure properties of regular languages, we used various models that characterize regular languages. To prove the closure property under union operation, we used regular expressions. We may as well use regular grammars or FA. However, for the efficiency of the proof, we need to choose a right model. Otherwise, the proof often appears difficult or sometimes impossible. For example, try to prove the closure property under complementation with regular grammars or regular expressions. There is no guideline available for the choice, except for building up related knowledge and experiences.

12

Rumination (1): language properties

Properties of Languages

• We saw the difference between the closure properties of regular languages and context-free languages. Another contrasting property is that the class of languages recognized by NPDA properly contains the class of languages recognized by DPDA, i.e., there are context-free languages that cannot be recognized by any DPDA. For example, it is impossible for a DPDA to recognize the context-free language {wwR | w ∈ {a, b}+ }. We know how to construct an NPDA recognizing this language. (Recall that a language recognized by an NFA if and only if it is recognized by a DFA.) Appendix D shows that, like the class of regular languages, the class of deterministic context-free languages (i.e., the languages recognized by DPDA) is closed under complementation.

Communication Deadlock “Who is calling?” was the answer to the telephone. “Watt.” “What is your name, please?” “Watt’s my name.” “That’s what I asked you. What’s your name?” “That’s what I told you. Watt’s my name.” A long pause, and then from Watt, “Is this James Brown?” “No, this is Knott.” “Please, tell me your name.” “Will Knott.” Whereupon they both hung up.

Break Time

- Raman -

13

Properties of Languages

Exercises

9.1 Let L be the language generated by the following regular grammar G. Construct a regular grammar whose language is LR. You should also show the procedure that you took to get your answer.

G : S → aA | bB B → aC | bE D → aE | bD | ε

A → bD | ε C → aC | bE | ε E → aE | bD

9.2 (a) Construct a regular grammar (i.e., right-linear) whose language is the complement of language L generated by the grammar G above. You should also show the procedure that you took to get your answer. (b) Construct a left-linear grammar that generates the same language generated by the grammar G above. 9.3 For two context-free grammars G1 and G2 below, (a) construct a context-free grammar whose language is the product L(G1)L(G2). (b) Construct a context-free grammar whose language is the union, L(G1) ∪ L(G2). You should also show the procedure that you took to get your answer.

G1 : S → aA | bB B → aC | bE D → aE | bD | ε

A → bD | ε C → aC | bE | ε E → aE | bD

G 2:

S → aA

A → Sb | b

14