Resources

Strings and Languages

Definitions.

Alphabet. Any non-empty finite set. We generally use either capital Greek letters $\Sigma ,\Gamma$ , or uppercase letters $A,B,...$ to designate alphabets.

Symbol. The members of an Alphabet.

Examples: $\Sigma_1=\{0,1\};\Sigma_2=\{a,b,c,d,e,f,g,h\};\Gamma=\{0,1,x,y,z\}$

String over an alphabet. A finite sequence of symbols from that alphabet.

Length of a string. If $w$ is a string over $\Sigma$, the length of $w$, written $|w|$, is the number of symbols that it contains. Some authors prefer to use $n_a(w)$ for indicating some $a$ characteristic applied on $w$.

Empty string. $|w|=\epsilon=\lambda=0$

Language. Set of strings. We generally use upper-case letters $A,B,...$ to designate languages.

Lexicographic ordering.

1. Shorter strings precede longer strings.

2. The first symbol in the alphabet precedes the next symbol.

Regular operations.

Let $A,B$ be languages:

Union: $A\cup B=\{w|w\in A\text{ or }w\in B\}$

Concatenation: $A\cdot B=\{xy|x\in A\text{ or }y\in B\}=AB$

$A^k=A \overset{\text{k times}}{ A...A},A^1=A,A^0=\{\epsilon\}$

Kleene star: $A^*=\{x_1...x_k|\text{ each }x_i\in A \text{ for } k\ge 0\}=A^0\cup A^1\cup A^2 \cup A^3 \cup...$, note $\epsilon\in A^*$ always.

Kleene plus: $A^+=A^1\cup A^2\cup A^3\cup...=V^*V$

Example. Let $A=\{good,bad\}$ and $B=\{boy,girl\}$

$A\cup B=\{good,bad,boy,girl\}$

$AB=\{goodboy,goodgirl,badboy,badgirl\}$

$A^2=\{goodgood,goodbad,badgood,badbad\}$

$A^*=\{\epsilon,good,bad,goodgood,bgoodbad,badgood,badbad,goodgood,good,goodgoodbad,...\}$

Worked examples

Homework

Models of computation

https://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation_Chapter4.pdf

Grammar

Interpreter

Formal grammar is a tool for syntax, not semantics.

Vocabulary

Grammar. A grammar is a 4-tuple $(V,T,S,P) ,$

where $V$ is a finite set of objects called variables,

$T$ is a finite set of objects, disjoint from $V$, called terminal symbols, in short terminals,

$S\in V$ is a special symbol called the start variable,

$P$ is a finite set of rules, called production rules, with each rule being a variable a string of variables and terminals.

BNF. A particular form of notation for grammar (Backus-Naur form).

CNF. A particular form of notation for grammar (Chomsky normal form).

Language generated by $G$. Let $G=(V,T,S,P) ,$ be a grammar. Then the set

is the language generated by G.

Production rules. If production rules are of the form

where $x \in (V \cup T)^+$, $y \in (V \cup T)^*$. The production rules are applied in the following manner: Given a string $w_1=uxv$

We say that $w_1$ derives $w_2$ o that $w_2$ is derived from $w_1$.

If $w_1\to w_2\to ...\to w_n,$

we say that $w_1$ derives $w_n$ and write

$w_1 \to^* w_n$. The * indicates an unspecified number of steps (including zero).

Chomsky normal form (CNF) example

$V=\{P,S,M\}$, $T=\{+,*,1,2,3,4\}$, $S\in V$

Backus–Naur form (BNF) example

$V=\{P,S,M\}$, $T=\{+,*,1,2,3,4\}$, $S\in V$

Grammar Hierarchy

Set view

Table view

https://www.cs.utexas.edu/users/novak/cs343283.html

Classification

• Acceptors

• Transducers

• Generators (also called sequencers)

https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40342.pdf

Worked examples

Steps to convert regular expressions directly to regular grammars and vice versa

https://cs.stackexchange.com/questions/68575/steps-to-convert-regular-expressions-directly-to-regular-grammars-and-vice-versa

FAQ

Are axioms in math equivalent to production rules in unrestricted grammars?

how could a CFG hold an unrestricted grammar (UG), which is turing complete?

https://stackoverflow.com/questions/61952877/chomsky-hierarchy-examples-with-real-languages?rq=1

Notes and references

[1] M. Johnson, “Formal Grammars Handout written,” 2012 [Online]. Available: https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/080 Formal Grammars.pdf. [Accessed: 28-Feb-2022]

Finite automata

Finite automata and their probabilistic counterpart Markov chains. Finite Automaton (FA) or Finite-State Machine. An automaton (Automata in plural).

• The computer is complex, instead, we use an idealized computer called a computational model.

• A finite automaton:

We feed the input string $01$ to the machine $M_1$, the processing proceeds as follows:

1. Start in state $q_1$.

2. Read 1, follow the transition from $q_1$ to $q_2$.

3. Read 1, follow the transition from $q_2$ to $q_1$.

4. Accept because $M_1$ is in an accept state $q_2$ at the end of the input.

The formal definition of a deterministic finite automaton (DFA)

A finite automaton is a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ where

1. $Q$ is a finite set called the states,

2. $\Sigma$ is a finite set called the alphabet,

3. $\delta:Q\times \Sigma\rarr Q$ is the transition function,

4. $q_0 \in Q$ is the start state, and

5. $F\subseteq Q$ is the set accept states, they are sometimes called final states.

The formal definition of a nondeterministic finite automaton (NFA)

A finite automaton is a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ where

1. $Q$ is a finite set called the states,

2. $\Sigma$ is a finite set called the alphabet,

3. $\delta:Q\times (\Sigma\cup\{\lambda\})\rarr P(Q)=\{R|R \subseteq Q\}$ is the transition function (P is a power set),

4. $q_0 \in Q$ is the start state, and

5. $F\subseteq Q$ is the set accept states, they are sometimes called final states.

Converting NFAs to DFAs

delta = {
  'state1': {
     'symbol1': {'state1', 'state2',...}
   }
}
# BFS
NFAToDFA(NFA)
   
         

FAQ

What is the difference between finite automata and finite state machines?

Pattern Matching

Extended finite-state machine

https://www.seas.upenn.edu/~lee/10cis541/lecs/EFSM-Code-Generation-v4-1x2.pdf

Automata and Grammar

Regular expressions to Automata

1. Generalized nondeterministic finite automaton.

def convert_to_regular_rxpression(G):
   if G.number_of_states == 2:
      return 

1. Solving right-linear equation by Arden’s rule.