| |
Dec 26, 2024
|
|
|
|
|
CS 5100 - Introduction to Formal Languages and Compilers
Practical and formal aspects of computing related to the lexical and syntactic analysis stages of compilation explored. Relationships among regular expressions, deterministic finite automata, and nondeterministic finite automata presented. Relationship between context-free grammars and pushdown automata also explored. Practical parsing algorithms examined, including bottom-up, town-down, and recursive descent strategies. Design of significant project using formal language concepts required.
Requisites:
Credit Hours: 3
Repeat/Retake Information: May not be retaken.
Lecture/Lab Hours: 3.0 lecture
Grades: Eligible Grades: A-F,WP,WF,WN,FN,AU,I
Learning Outcomes:
- Students will become familiar with the basic top-down, bottom-up, and recursive descent parsing techniques.
- Students will develop the ability to apply automata conversion algorithms
- Students will develop the ability to construct a bottom-up, top-down, or recursive descent parser for simple context free grammars.
- Students will develop the ability to construct context free grammars for simple languages, as well as for constructs in programming languages.
- Students will develop the ability to design finite automata for certain languages.
- Students will develop the ability to implement the automata conversion algorithms in a programming language like C or C++.
- Students will develop the ability to minimize finite automata.
- Students will develop the ability to show that a grammar is ambiguous.
- Students will develop the ability to show that a language is not regular via the pumping lemma or the MyHill-Nerode theorem.
- Students will develop the ability to show, in certain cases, that languages are not context-free.
- Students will gain an understanding of the basic definitions of context free grammars.
- Students will gain an understanding of and the ability to use the basic terminology concerning strings, languages, and functions.
- Students will gain an understanding of and the ability to write regular expressions. In particular, students should be able to design regular expressions that have applications in programming languages.
- Students will gain an understanding of derivation trees and the concept of ambiquity in context free grammars.
- Students will gain an understanding of the basic algorithms involved in finding minimum state automata.
- Students will gain an understanding of the basic algorithms to convert among the various finite automata and regular expressions.
- Students will gain an understanding of the basic pushdown automata model and its connection to predictive parsing.
- Students will gain an understanding of the various deterministic and nondeterministic finite automata.
- Students will gain an understanding that certain languages cannot be recognized with context free grammars.
Add to Portfolio (opens a new window)
|
|
