CPSC 323: Compilers and Languages Design Notes

CPSC 323: Compilers and Languages Design Notes

Instructor and Course Details

  • Course: CPSC 323: Compilers and Languages Design
  • Instructor: Mr. Mohit Patni, Teaching Associate
  • Contact: zz-mpatni@Fullerton.edu
  • References: Prof. Doina Bein & Prof. James Choi

Grammar

  • Definition of Grammar:
    • Grammar is a set of rules that define whether a particular sentence is part of a language.
    • Correct grammatical structure indicates that the sentence is well-formed and adheres to the conventions of the language.

Example of Grammar

  • Sentence: "Here is your coffee."
  • Incorrect Sentence: "Is here your coffee."
    • While the second example is a sentence, it does not conform to the rules of English grammar.
  • Function: Grammar determines whether a string (sequence of symbols) is part of a language or not.

Automata

  • Definition: Automata refers to a mathematical model or machine that helps in recognizing whether a string is part of a language.
  • Type of Strings: Automata can be classified based on the number of strings.

Finite Automata

  • Characteristics:
    • Finite: A fixed number of strings, or a language that consists of a finite collection of strings.
    • Examples:
    • If the alphabet is $ ext{{ exttt{a, b}}}$, possible language can be {aa, ab, ba, bb} which is finite.

Infinite Automata

  • Definition: A language capable of producing an infinite number of strings using the given alphabet.
  • Example: Using the alphabet $ ext{{ exttt{a, b}}}$, strings like a, aa, aaaa, ob, abab, ba, baba, etc., can be generated infinitely.

Membership Question

  • A question arises: Is the string {abba} part of the language or not?
    • To check membership in infinite languages, one cannot simply store all strings in memory for comparison due to their unlimited nature.

Types of Finite Automata

Deterministic Finite Automaton (DFA)

  • Definition: A machine where:
    • For each state and each input, there is exactly ONE next state.
    • It operates without ambiguity, hence "Deterministic" implies predictability.
Example: Traffic Light
  • States: Red, Yellow, Green
  • Input: Timer
    • Transition: From Red → always goes to Green;
    • From Green → always to Yellow;
    • From Yellow → always to Red.

Non-deterministic Finite Automaton (NFA)

  • Definition: A machine where:
    • For a state and an input, there can be MORE THAN ONE possible next state.
    • Includes ε (epsilon) moves where the automaton can move without reading any input.
Example: Choosing a Road
  • Scenario: Arriving at a junction where:
    • One road leads to the Mall,
    • Another to the Park.
    • Non-deterministic choice leads to trying multiple roads to achieve success.

Components of Automata

  • States: Set of all finite states in the automaton.
  • Alphabet ($Σ$): Set of symbols or inputs.
    • Example: $Σ = ext{{ exttt{a, b}}}$ or $Σ = ext{{ exttt{0, 1}}}$.
  • Transition Function ($S$ or $ ext{Delta}$): Mapping of states to transitions.
  • Start State ($q_0$): Initial state of the automaton.
  • Final State ($F$): Accepted states where if an automaton ends up, the string is accepted.

Examples of DFA

Example 1

  • Objective: Construct a DFA that accepts strings starting with 'a'.
    • Alphabet Set: Σ = {a, b}
    • Accepted string must begin with 'a'.
    • If a string starts with 'b', it will transition to a dead state.

Example 2

  • Objective: Construct DFA that accepts strings containing 'a'.
    • If the string is just 'b', it should lead to the dead state.
    • The DFA must recognize presence of 'a' anywhere in the string. If only 'b's are found, it gets trapped.

Try It Yourself

  • Challenge: Construct a DFA that accepts strings starting with 'a' and ending with 'b'. Example: {ab}.

NFA Example

Objective

  • Design an NFA for all binary strings where the 2nd last bit is 1.
    • Alphabet: {0, 1}
    • Accepted cases: Strings like 10, 01, 11 where the condition is met.
    • Rejected cases: Strings like 00, where the 2nd last bit isn’t 1.
    • State Requirement: Minimum length must be 3 states to accommodate the second last bit.

State Design

  • Functionality: The second state in NFA must accept multiple combinations of bits.
  • Transitions: Design where each state can either transition to another state or loop back based on the input.

Conclusion

  • Understanding DFAs and NFAs is crucial in Compiler Design for string recognition and language validation purposes. Continuous practice with constructing automata will enhance comprehension of theoretical principles.