Description

Problem 1: (20 points) Use the pumping lemma to show that the following languages are not regular.
a.

If we assume that 1 is regular, the Pumping Lemma definition tells us that any string in 1 can be ‘pumped’ at least a ‘pumping length’ of , then divided into three pieces = . For it to be regular, it must satisfy the following conditions:
(1)
(2)
(3) ||
We can test these conditions by doing the following:
• Assume is regular
• Let be the pumping length
• Choose a string in language 1 to test: = 012 o As we assume 1 is regular, is a member of 1
o Because || = 3, and , then ||
o Since both statements above are true, the Pumping Lemma definition tells us that can be split into three pieces =
• For conditions (2) || and (3) || to be met, piece must contain only 0’s o For example, consider
012 = 031323
031323 = 000111222
o For || , can only contain 0’s
000111000

• According to condition (1) o assume ⅈ = 2

o Visual Representation
00000111000

o
▪ However, there is no possible division of 00000111000 that will result in the required 012 format. This is evident in the visual representation above as it has the format 051323 and . As increases, this also remains true since additional zeros are placed at the beginning of the string, creating a further imbalance between 0 and 12 (which should be identical ’s). Therefore, language 1 does not meet condition (1) for Pumping Lemma.
Since not all pumping lemma conditions are met, the assumption that 1 is regular is contradicted and proves that 1 is not regular.
Q.E.D
b. 2={|

If we assume that 2 is regular, the Pumping Lemma definition tells us that any string in 2 can be ‘pumped’ at least a ‘pumping length’ of , then divided into three pieces = . For it to be regular, it must satisfy the following conditions:
(1)
(2)
(3) ||
We can test these conditions by doing the following:
• Assume 2 is regular
• Let be the pumping length
• Choose a string in language 2 to test: = o As we assume 2 is regular, is a member of
o Because || = 3 + 3, and , then ||
o Since both statements above are true, the Pumping Lemma definition tells us that can be split into three pieces =
• For conditions (2) || and (3) || to be met, piece must contain only ’s o For example, consider
= 333
333 =
o For || , can only contain ’s

• According to condition (1) o assume ⅈ = 2

o Visual Representation

o
▪ However, there is no possible division of that will result in the required format. This is evident in the visual representation above as it has the format 533 and . As increases, this also remains true since additional ’s are placed at the beginning of the string, creating a further imbalance between the first = and the last two = 33 (which should be identical ’s). Therefore, language 2 does not meet condition (1) for Pumping Lemma.
Since not all pumping lemma conditions are met, the assumption that 2 is regular is contradicted and proves that 2 is not regular.

Q.E.D
Problem 2: (20 points) Give context-free grammars that generate the following languages. In all parts = {0,1}
1. {w | w starts and ends with the same symbol}

→ | | |
→ 0 | 1 |

2. {w | the length of w is odd|

→ | |
Problem 3: (10 points) Please design and draw a PDA which recognizes {ⅈ |
PDA 6-Tuple (, , , , 0, )
= {1, 2, 3, 4, 5, 6, 7}
= {, , } = {$, }
0
= {7} Set of States
Input Alphabet
Stack Alphabet
Start State
Set of Accept States

Problem 4: (10 points) Convert the following CFG into an equivalent CFG in Chomsky normal form, using the procedure given in Theorem 2.9.

→ | |
→ 00 |

→
→ | |
→ 00 |

1. Create new start variable

2. Eliminate all -rules of form →
→ |
→ | | | | |
→ 00
3. Eliminate all unit rules of form →

→ |
→ | | 00 | | | |
→ 00
remove →

→ |
→ | 00 | | | |
→ 00
remove →

→ | | | | | |
→ | 00 | | |
→ 00
remove →

4. Replace each rule → u , where and ⅈ is a variable or terminal symbol
→ | | | | | |
→ | | | | |
→ 00
→ AB
replace

→ | | | | |
→ | | | |
→ 00 |
→ AB
→ 0
replace

5. Final CFG in Chomsky Normal Form

→ | | | | |
→ | | | |
→
→ AB
→ 0

Problem 5: (10 points) Use pumping lemma to show that is not context free.

The Context- Free Pumping Lemma definition tells us that any string in can be ‘pumped’ at least a ‘pumping length’ of , then divided into five pieces = . For it to be regular, it must satisfy the following conditions:
(1)
(2) || (3) ||
We can test these conditions by doing the following:
• Assume 3 is a context-free language (CFL)
• Let be the pumping length
• Choose a string in language 3 to test: o As we assume 3 is CFL, is a member of o Because || = 4, and 4 , then ||
o Since both statements above are true, the Pumping Lemma definition tells us that can be split into five pieces =
• Case 1: and contain only one type of symbol o Testing conditions (2) || and (3) || under Case 1
▪ Assume

• Split = , with ||

||

o Testing condition (1)
▪ assume

• Visual Representation
000000011111110000011111

•
o There is no possible division of 000000011111110000011111 that
will result in the required 0101 format. This is evident in the visual
representation above as it has the format 07170515 and . As increases, this also remains true since additional zeros and ones are placed at the beginning of the string, creating a further imbalance between the first 01 and the second 01 (which should be identical
’s). Therefore, language 3 does not meet condition (1) for Pumping Lemma when split in such a way that and contain only one type of symbol.
• Case 2: Either or contain more than one type of symbol o Testing conditions (2) || and (3) || under Case 2
▪ Assume

• Split = , with ||

||

o Testing condition (1)
▪ assume

• Visual Representation
000001011111110000011111

•
o There is no possible division of 000001011111110000011111 that
will result in the required 0101 format. This is evident in the visual representation above as it has the format 051101170515 and
. As ⅈ increases, this also remains true
since contains more than one type of symbol; as ⅈ is pumped, the string places 1’s in the incorrect spot, disrupting the language format entirely. Therefore, language 3 does not meet condition (1) for Pumping Lemma when split in such a way that either or contain more than one type of symbol.
Since not all pumping lemma conditions are met in either Case 1 or Case 2, the assumption that 3 is a CFL is contradicted and proves that 3 is not context-free.

Q.E.D
Problem 6: (10 points) Answer the following two questions:
• Briefly describe how regular language is used for lexical analysis in a compiler.
o Regular Language is used by the lexical analyzer to tokenize the source file (Character Stream), using the string patterns defined by the regular language as the scope for the tokens. These tokens define basic program syntax and are used to verify errors in code. For example, if the code contains any characters which do not match a token pattern (valid syntax), a Lexical Error is raised. Examples of Lexical Errors are spelling errors, typos, and illegal characters. After these tokens are sent into a Token stream, they are sent to the Parser, and undergo syntax analysis.
• Briefly describe how context free language is used for parsing (syntax analysis) in a compiler.
o Context-free language is used for parsing in a compiler to transfer the tokens from the Token Stream into a Parse Tree while verifying the code is syntactically correct. While lexical analysis focuses on individual words, syntax analysis focuses on how these words work together and whether they adhere to the correct grammar rules. Context-free language is what specifies these grammar rules. If the code contains any deviations to these rules, such as structurally or syntactically, a Syntax Warning/Error is raised. Examples of Syntax Errors are unbalanced parenthesis, missing operators, and indentation errors. After Syntax Analysis, the code undergoes Semantic Analysis.
Problem 7: (20 points) Programming Assignments
a. (4 Points) Describe GCC Intermediate Files o hello.c
• This is the original source code file in C. It is a simple program written using the coding language C that prints the line “hello world” and newline character to the console.
o hello.i
• This is the GCC preprocessor output file. The preprocessor begins transforming the original source file using Lexical Analysis. Some operations completed during this step includes: removing comments, substitutes macros for their equivalent values, and compiles all conditionals.
o hello.s
• The assembly code for the source file. It contains the source file equivalent written in low-level assembly language.
o hello.o
• This is the object file. It contains the machine code (binary representation) equivalent of the source code. When there are multiple source files, multiple object files are created. These are then linked together to create the executable.
o hello
• This is compiled and linked executable which can be ran using “./hello”. When the program is run, it executes the code originally written in hello. c – it prints the line “hello world” and newline character to the console.

CSC720 Theory of Computation Conway, Kiera b. Included in HW folder.