• Applying a rule means replacing the left side with the right side.

Example: Grammar for the Lalelu Language

• Every word in the Lalelu language consists of 3 syllables which can be "la," "le," or "lu."
• Every word must end in "lu."
• Examples of words in the language: "laelu," "lulelu," "lalalu."
• G = (V, Σ, P, S)
  • V (variables) = {S, A}
  • Σ (alphabet) = {la, le, lu}
  • P (productions/rules) =
    • S → AAlu
    • A → la
    • A → le
    • A → lu

Derivation Process

• Begin with the start variable and apply rules successively to generate a word.
• Example derivation:
  • S → AAlu
  • AAlu → laAlu
  • laAlu → lalelu
  • S → AAlu
  • AAlu → leAlu
  • leAlu → lelu
  • S → AAlu
  • AAlu → lula
  • lula → lulu
• Key rule: AAlu ensures word has 3 syllables and ends in 'lu'
• Possible syllables are assigned: A → la | le | lu | AA | ε (epsilon)

Example 2

• G = (V, Σ, P, S) with
• V = {S, A, B}
• Σ (alphabet) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
• P (productions/rules) =
• S → BAB
• A → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
• A → AA
• B → 0 | 2 | 4 | 6 | 8
• Examples generated: 7, 8, 234, 58
• Cannot generate single digit values
• Always create pairs
• Examples:
  • S → BAB
  • A → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Chomsky Hierarchy

• Grammars (and the languages they generate) can be of Chomsky Type 0, 1, 2, or 3.
• The higher the type, the "simpler" the grammar.

Definitions of Chomsky Types

• Every grammar is Type 0.
• A grammar is Type 1 (context-sensitive) if, for all rules: |l| ≤ |r|.
• A Type 1 grammar is Type 2 (context-free) if, in addition, for all rules l ∈ V (non-terminal) r, the left side always contains only a single variable, never a terminal.
• A Type 2 grammar is Type 3 (regular) if, in addition, for all rules, r ∈ Σ or r ∈ ΣV (the right side is either a single terminal or a terminal followed by a variable).
• A language is of type i if there is a grammar of type i that generates it.

Notes on Chomsky Hierarchy

• Exception: r = ε (empty string) is allowed for every type.
• Context-free grammars only allow rules of the form A -> X, where the left side contains only a variable.
  • This allows A to be replaced by X regardless of context.
• NAV -> uxv is context-sensitive; A can only be replaced by x if it is between u and v.
• The smaller the type number, the more powerful the language.
• Example: The Lalelu grammar is of type 0, 1, 2, i.e., context-free. The Lalelu language is even of type 3, i.e., regular, because there is a regular grammar that generates it.
• G = (V, Σ, P, S) with
  • V = {S, a, b}
  • Σ = {la, le, lu}
  • P = {
  • S → laa
  • S → lea
  • S → lua
  • a → lab
  • a → leb
  • a → lub
  • b → lu}

Regular Expressions

• Alternative way to describe regular languages which consist of characters from the underlying alphabet, parentheses and operators.
• Operators:
  • | : or
  • * : repetition, arbitrarily often
  • + : repetition at least once

Precedence Rules

• (...)
• concatenation
• |

Examples

• (ab|c)* is equivalent to (a|b|c)* (concatenation takes precedence over |)
• ∑ = {a,b}
  • a*|b* matches aa, bbbb, or ε (empty string)
  • a+ |b+ matches aa, bbbb (but without ε)
  • b*ab* matches a, ba, bbabbb (exactly one a and arbitrarily many b's)
  • (a|b)* matches ε* (any set of words)
  • (a|b)(a|b) matches aa, bb, ab, ba (exactly two letters)
  • b*a|b*|b* matches babb, b, ε (at most one a)
• (ha)+ ! (parentheses can be omitted because ha is defined as a letter within the alphabet)
• ∑ = {0,1,2,3,4,5,6,7,8,9}
  • (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* matches any number.
  • (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(0|2|4|6|8) matches any even number.
• The operator + could be omitted, since x+ = xx*.

Automata

• An automaton is a 5-tuple A = (Q, q0, Σ, δ, F) with:
  • Q (set of states) is a finite set of states.
  • q0 (start state) is the start state.
  • Σ (alphabet) is the input alphabet.
  • δ (transition function) is a transition function.
  • F (acceptance states) is a set of final states.
• Process begins in start state; input symbols transition the process between states.
• If the process ends in an accepting state, the input is accepted.
• Finite automata can only depict regular languages.
• An automaton is complete if every state has a defined transition for every input.

Examples

• Example 1: Lachsprache Automaton
  • Automaton is not complete and not deterministic (two possible paths for input 'a' from state '90).
  • Can make deterministic automaton by completing the initial automaton
• Deterministic: An automaton is deterministic if each input has exactly one resulting state.
  • Example 2: Words over ∑ = {0, 1} that end in "00". The non‐deterministic automaton can be converted as before.
• The transition function can be drawn as a table rather than a diagram. The table defines an initial state plus possible inputs and proceeding states..
  • The example given details words with an average number of 'a's

Minimization of Automata

• For every finite automaton, there is a uniquely determined minimal automaton that accepts the same language and has a minimal number of states.

Algorithm for Minimizing Automata

1. Create a state pair table for all pairs of states (qi, qj) where i ≠ j.
2. Mark all pairs where exactly one state is a final state.
3. Mark all pairs for which there is an a ∈ Σ such that the successor state pair is already marked.
4. Repeat step 3 until no more changes occur in the table.
5. Merge the unmarked pairs

Result

• Pairs that can/cannot be merged are marked.

Pushdown Automata (PDA)

• Finite automaton + memory ("stack"), accepts context-free languages.
• A pushdown automaton is a 7-tuple M = (Q, q0, Σ, Γ, #, δ, F)
  • Q = finite set of states
  • q0 = start state
  • Σ= input alphabet
  • Γ = stack alphabet

  • = stack bottom symbol

  • δ = transition function
  • F = set of final states
• Stack initially contains only the bottom symbol. Each input symbol is read, and the top stack symbol is read and removed. New symbols can be placed on the stack.
• Example: Lets store as and then loop through all b
• L accepts any number of a, followed by any number of bis

Exercises

Task 1

• Question: Given an automaton, determine its properties and the language it accepts.
• The prompt presents an automaton A = (Q, q0, Σ, δ, F) with Σ = {a, b} graphically.
• The task is to define the sets Q and Σ, create the transition function δ in table form, determine if the automaton is complete and/or deterministic, and decide if it accepts certain words.
• Additionally, the prompt asks for a word of length 5 that the automaton accepts, a word of length 5 it doesn't accept, and a verbal description of the language produced by the automaton.
• Solution:
• Q = {q0, q1, q2}, F = {q2} (The set of states and the set of final states)
• The state transition table would map from each (state, input) pair to the next state.
• Complete and Deterministic: The student needs to determine whether all transitions are defined and whether each input leads to a unique state.
• Word Acceptance: The student correctly identifies whether some words are accepted by the automaton.
• Language Description: The language starts with 'a' and ends with 'b'
• **

Task 2

• Automaton Specification: Describes an automaton. Task is to draw it and determine its properties.
• Task: Given A = (Q, q0, Σ, δ, E) with Q = {q0, q1, q2, q3}, Σ = {0, 1}, E = {q1, q2}. The task is to specify the transition function δ:
• draw the automaton diagrammatically
• determine whether the automaton is complete and/or deterministic
• decide whether various words are accepted or not. The language it accepts
• **

Remaining Tasks

• Task 3:
• Design automata for specific binary language characteristics.
• Create an automaton that accepts all binary numbers (without leading zeros).
• Design an automaton that accepts binary numbers divisible by 2 (with and without leading zeros)
• Task 4: Design an automaton that accepts times in the format hh:mm (e.g., 13:23 or 03:00).
• Task 5: Design an automaton that accepts numbers divisible by three. Note that a number is divisible by three if the sum of its digits is divisible by three.

Exercises on Minimizing Finite Automata

• Task: is to minimize given automata A = (Q, q0, Σ, δ, E) and describe the accepted language verbally and with a regular expression. This involves combining equivalent states to reduce the complexity of the automaton. The prompts include multiple automata