京都大学 情報学研究科 知能情報学専攻 2023年8月実施 専門科目 S-6

Author

itsuitsuki

Description (English)

We consider a grammar , where , and are a finite set of terminal symbols, a finite set of nonterminal symbols, a finite set of production rules, and the start symbol, respectively.

Q.1

The following is a description on context-free grammar. Fill the blanks (1), (2), and (3).

• A grammar is a context-free grammar when, for each production rule in , and . A language on is a context-free language when it is generated by a context-free grammar .

Q.2

Prove that and are context-free languages.

Q.3

Prove that the class of context-free languages is closed under concatenation by constructing from the context-free grammars and generating and , respectively.

Q.4

Prove that the class of context-free languages is closed under union by constructing from the context-free grammars and .

Q.5

is not a context-free language. By using this fact prove that the class of context-free languages is not closed under complement .

Q.6

Prove that the class of context-free languages is not closed under difference .

Kai

Q.1

(1):

(2):

(3): (by definition, it's not )

Q.2

We construct a grammar that can generate all strings in a corresponding language, where all strings generated by the grammar are in the language.

For , we construct a CFG (context-free grammar)

and for , a string in the language can be generated by applying once , times of , times of , once and once by order.

For a string generated, say , it must be in by the reversed logic above.

So is a CFL (context-free language).

Similarly, by a CFG

is generated by , thus being a CFL.

Q.3

By constructing a new CFG

every generated string has a part of substrings (at left) in (derived from ), while the right part is in derived from , forming . Every string in can also be generated by by separating into 2 parts and finding the corresponding and rules from and .

So can generate and it is a CFL.

Q.4

By constructing a new CFG

every generated string either falls in by applying in the first step or falls in by ; every string in language can find the generation rules in or plus the or rule.

So can generate and it is a CFL.

Q.5

Since

because in RHS, the number of a's and b's must be equal and that of b's and c's are also equal, so the intersection is by definition , and is not a CFL, if the class of CFLs are closed under complement, then for CFL, and are CFLs, and is a CFL, and thus

is a CFL (contradiction), hence under complement the class is not closed.

Q.6

Since is a CFL with a context-free grammar of , an arbitrary , a rule set with every possible rule based on and and a start symbol , let be a CFL, assume under difference the class of CFLs is closed, then is a CFL.

However, is by definition not necessarily a CFL because in Q.5, complement cannot make the class closed (contradiction).

So under difference the class of CFLs is not closed.