tailieunhanh - Chapter 5: Context-Free Grammar

Chương 5 của bộ Slide tiếng Anh môn học lý thuyết automata và ngôn ngữ hình thức đầy đủ của trường ĐHBK . Bộ Slide này có tổng cộng 7 chương. | Chapter 5: Context-Free Grammar Quan Thanh Tho qttho@ Non-regular Languages Not all languages are regular. L1 = {anbn | n 0} is not regular. L2 = {(), (()), ((())), .} is not regular. some properties of programming languages Context-Free Grammars G = (V, T, S, P) Productions are of the form: A x A V and x (V T)* CFG and Regular Language A regular language is also a context-free language. Why the name? Example G = ({S}, {a, b}, S, P) P = { S aSa S bSb S } S aSa aaSaa aabSbaa aabbaa L(G) = {wwR | w {a, b}*} Example G = ({S, A, B}, {a, b}, S, P) P = { S abB A aaBb B bbAa A } S abB abbbAa abbbaaBba abbbaabbAaba abbbaabbaba Example L = {anbm | n m} is context-free. G = (?, {a, b}, S, ?) P = { S AS1 | S1B S1 aS1b | A aA | a B bB | b } Example G = ({S}, {a, b}, S, P) P = { S aSb | SS | } S aSb aaSbb aaSSbb aaabSbb aaababbb L(G) = ? Derivations G = ({S, A, . | Chapter 5: Context-Free Grammar Quan Thanh Tho qttho@ Non-regular Languages Not all languages are regular. L1 = {anbn | n 0} is not regular. L2 = {(), (()), ((())), .} is not regular. some properties of programming languages Context-Free Grammars G = (V, T, S, P) Productions are of the form: A x A V and x (V T)* CFG and Regular Language A regular language is also a context-free language. Why the name? Example G = ({S}, {a, b}, S, P) P = { S aSa S bSb S } S aSa aaSaa aabSbaa aabbaa L(G) = {wwR | w {a, b}*} Example G = ({S, A, B}, {a, b}, S, P) P = { S abB A aaBb B bbAa A } S abB abbbAa abbbaaBba abbbaabbAaba abbbaabbaba Example L = {anbm | n m} is context-free. G = (?, {a, b}, S, ?) P = { S AS1 | S1B S1 aS1b | A aA | a B bB | b } Example G = ({S}, {a, b}, S, P) P = { S aSb | SS | } S aSb aaSbb aaSSbb aaabSbb aaababbb L(G) = ? Derivations G = ({S, A, B}, {a, b}, S, {S AB, A aaA, A , B Bb, B }) 1 2 3 4 5 S AB aaAB aaB aaBb aab S AB ABb aaABb aaAb aab 1 2 3 4 5 1 4 2 5 3 Leftmost and Rightmost Derivations Leftmost: in each step the leftmost variable in the sentential form is replaced. Rightmost: in each step the rightmost variable in the sentential form is replaced. Example G = ({S, A, B}, {a, b}, S, {S AB, A aaA, A , B Bb, B }) 1 2 3 4 5 S AB aaAB aaB aaBb aab leftmost S AB ABb aaABb aaAb aab 1 2 3 4 5 1 4 2 5 3 Ordered Tree for a Production A abABc A b a c B A ordered tree Derivation Tree Let G = (V, T, S, P) be a context-free grammar. An ordered tree is a derivation tree iff: The root is labeled S. Every leaf has a label from T { }. Every interior vertex has a label from V. A vertex has label A V and its children are labeled a1, a2, ., an iff P contains the production A a1 a2 . an. A leaf labeled has no siblings. Partial Derivation .