Context-Free Languages

title: 'Context-Free Languages' date: '2021-02-14'

Context-Free Languages

Context-Free Grammar (CFG)

, where

1. is a finite set of variables
2. is a finite set of terminals
3. is a finite set of rules, with each rule being a variable and a string of variables and terminals
4. is the start variable

Say derives (written ) if . Suppose is a CFG. Then the language of D is

A language is context free if it can be generated by some context free grammar Ambiguity: A grammar can generate a same string in different ways

Theorem (context free languages): The set of languages recognized by pushdown automata the set of languages you can design a CFG to recognize.

Pushdown Automata

A pushdown automata is a 6-tuple , where

• is finite set of states
• is finite input alphabet
• is finite stack alphabet
• is the start state
• is the set of accept states

The process of computation by pushdown automata accepts input where and sequence of states , strings exists with following conditions:

1. starts with and : with start state and empty stack
2. For , we have : moves properly according to state, stack and next input symbol

"": when the machine is reading from the input, replace on top of stack by a

To test for an empty stack, placing a $$$ on the stack.

Equivalence with Context free grammars

Corollary: Every regular language is context free.

Pumping lemma for CFLs

Theorem: If a language is CFL, then there is a number where, if is any string of of length at least , maybe divided into 5 pieces: satisfying:

1. For each
2. > 0: either or is not emptyset

Idea: Suppose a string derived from CFG and has a parse tree. Height of parse tree of is , and is the maximum number of symbols on the right side of a rule, then length of is at most . The parse tree must contain some path from start variable to one of the terminal symbols at a leaf. has to be bigger than the number of variables on the path. Because of pigeonhole principle, some variable symbol must repeat.

Show a language is context free

1. By constructing a context free grammar:

Proof by induction: Base Case (n=0 or 3): 2nd, 3rd, 4th, 5th rules generate aab, aba, baa, Induction hypothesis: Suppose all strings in of length can be generated Induction step: Let be a string of length in . WTS can be generated by the CFG

• Case 1: There is a segment of string in , called which is in . can be partitioned into concatenated with , where and are in . , by induction hypothesis the first generates and the second generates .
• Case 2: There is no segment of that is in . Suppose the last character is , then this must be counterbalanced by two 's. If the two 's occur before the first two characters, we can split into and and we are back in case 1.
• Case 3: There is no segment of that is in . Suppose the last character is , then this must be counterbalanced by and , and one of them must be the first character. If is first then must be next, . If is the first then an extra must be somewhere in the middle: , where are in . Use .

HW Problems

hw2p4