Formal Languages & Automata 1

Basic

Kleene Star/Clousre ($\sum^*$)

• Unary Operator on the symbol set $\sum$
• Infinite set of all possible strings of all possible lengths over the set $\sum$, including the
  empty string $\lambda$
• eg. For $\sum= \bigl\{ a,b \bigr\} ,\sum^*=\bigl\{ \lambda,a,b,aa,bb,ab,ba,\dots\bigr\}$

Kleene plus($\sum^+$)

Excluding the $\lambda(\text{Empty String})$

Languages

Languages are subsets of the Kleene star set $\sum^*$ over some alphabet set $\sum$, which could be finite or infinite.

• Syntax

• Semantics

• Natural Languages

• Formal Languages

Formal Language

Formal language is specified by a well-defined set of rules of syntax;

Vocabulary

A vocabulary (alphabet) $V$ is a finite, nonempty set of elements called symbols.

A word (sentence) over V is a string of finite length of elements of $V$

The empty string or null string, denoted by $\lambda$, is the string containing no symbols

The set of all words over $V$ is denoted by $V^*$

A language over $V$ is a subset of $V^*$

Phrase-Structure

$G = (V, T, S, P)$ consists of:

• a vocabulary $V$

• a subset $T$ of $V$ consisting of terminal symbols

• a start symbol $S$ from $V$

• a finite set of productions $P$.

The set $V - T$ is denoted by $N$.

nonterminal symbols : Elements of $N$ are called

Every production in $P$ must contain at least one nonterminal on its left side.

A Language

Let $G = (V, T, S, P)$ be a phrase-structure grammar.

The language generated by $G$ denoted by $L(G)$ is the set of all strings of terminals that are derivable from the starting state $S$.

$L(G)={w\in T^* | S \stackrel{\text{*}}{\Rightarrow}w}$

Four Types of Grammar

• Turning Machines Unrestricted or Phrase-Structure grammar
  • $u \rightarrow v, u\in V^*N V^*$
• Context sensitive grammar
  • $u \rightarrow v,|u| \leq|v|, \text{length increasing grammar}$
  • $\alpha$ $N$ $\beta$ $\rightarrow$ $\alpha$ $\chi$ $\beta$
  • $\alpha,\chi,\beta \in V^{*}$
• Push Down Automata - Context-Free grammar
  • $A \rightarrow \alpha, \text{where }A \in T \text{ and } \alpha \in V^*$
• Finite State Automata
  • $A \rightarrow aB,$ $A,B \in T$
  • $A \rightarrow b,$ $b \in T \text{ or }\lambda$

Decidable Languages

• If exist a TM that accepts and halts on every input string $S$, then the language is called decidable or recursive.

• Every decidable language is Turing-Acceptable.

• If all yes instances of problem $P$ have decidable language $L$, then the decision problem $P$ is decidable.

Undecidable Languages

• There does not exist a TM that accepts the language and makes a decision on every input string $S$ for undecidable languages(Tho a TM might make a decision on some input strings).

• If all yes instances of problem $P$ have languages $L$ that are undecidable, then $P$ is termed undecidable

• Inexpressible languages not recursive languages, but sometimes recursively enumerable languages.

Derivation(Parsing)

Application of a series of grammar productions or rules

Ultimately result in a string composed entirely of terminal symbols.

• leftmost derivation: At each step, only rewrite the leftmost non-terminal symbol
• rightmost derivation(Canonical derivation): ⬆️RightMost

Unambiguous Grammar：Only one sentence corresponding to each parse tree

Ambiguous Grammar: Allow multiple parse trees for serveral sentences

Mildly context-sensitive language:

• Allow for limited forms of context sensitivity beyond what is expressible by
  context-free grammars
• Include tree-adjoining grammars, linear context-free rewriting systems, and range concatenation grammars.

Sub-Regular Hierarchy:

• Include classes such as finite-state languages, star-free languages, visibly pushdown
  languages, and others.
• Each level represents a different degree of complexity in terms of the computational resources
  required to recognize or generate languages within that level.

Regular Languages

Regular Grammar (Type 3 Grammar):

A type of formal grammar characterized by production rules of the form $A \rightarrow Bx$ or $A \rightarrow x$
where $A, B \in N$ (non-terminal symbols) and $x \in \Sigma$ (terminal symbols).

Also referred to as a finite-state grammar (FSG) or a left-linear grammar.
If the production rule is of the form $A \rightarrow xB$, then it’s called a right-linear grammar.
Languages generated by these grammars are recognized by finite automata.

$B$ is a non-terminal symbol.

• In a right-linear grammar: $A \rightarrow xB$ or $A \rightarrow x$,

• In a left-linear grammar: $A \rightarrow Bx$ or $A \rightarrow x$,

• They are the most restrictive, allowing only a single non-terminal symbol on each side.

Arden’s Theorem:

Arden’s theorem is primarily used to find regular expressions for finite automata.

Pumping Lemma for Regular Languages:

To prove that specific languages are not within a given language class.
Cannot determine if a language is in a given class, as satisfying the lemma is a necessary but not sufficient condition for membership in a class.

Context-Free Language (CFL)
Context-Free Grammar(Type 2 Grammar):

All rules have the form $A \rightarrow \alpha$, where $A \in N$ and $\alpha \in (N \cup \Sigma)^*$.

These languages are recognized by pushdown automata.

Ambiguity in Context-Free Languages:

If a context-free grammar $G$ has more than one parse tree for a string $w \in L(G)$, it is said to be
ambiguous. For some strings generated by this grammar, there are multiple rightmost or leftmost derivations.

Pumping Lemma for Context-Free Languages:

Similar to the pumping lemma for regular languages, it’s used to check if a grammar is context-free. It’s based on the
pigeonhole principle.

Closure Properties of Context-Free Languages:

Under operations like Union, Concatenation, and Kleene Star, context-free languages remain closed.

Context-Sensitive Language (CSL):
Context-Sensitive Grammar (Type 1 Grammar):

The difference between the left and right sides of the derivation rules is reflected in
the middle of the strings, representing context sensitivity in everyday life.
If the production rules of a grammar $G$ satisfy the form $\alpha A \beta \rightarrow \alpha \gamma \beta$
where $A \in N$, $\alpha, \beta, \gamma \in (N \cup \Sigma)^*$, and $\gamma$ contains at least one character, then $G$ is called a context-sensitive
grammar.

Recognized by linear-bounded automata.

Recursively Enumerable Languages:
Unrestricted Grammar (Type 0 Grammar):

The production rules satisfy $\alpha \rightarrow \beta$,
where $\alpha$ and $\beta$ are strings, $\alpha$ contains at least one non-terminal symbol, and it’s not an
empty string. Languages generated by these grammars are recognized by Turing machines. Due to their generality and lack
of restrictions, they cannot describe the syntax of programming or natural languages.

Backus-Naur Form

Context Free

eg. Identifier

<identifier> ::== <letter> | <identifier><letter> | <identifier><digit>

<letter> ::== a|b| \cdots |y|z   

<digit> ::== 0|1|2|3|4|5|6|7|8|9

Automata

Finite-state machine

A finite-state machine $M = (S,I,O,f,g,s_0)$ consists of a finite set $S$
of states,

$I$: a finite input alphabet
$O$: a finite output alphabet
$f$: a transition funciton that assigns to each state and input pair a new state
$g$: an output function that assigns to each state and input pair an output
$s_0$: an initial state

Deterministic Finite Automata(DFA)

• In a DFA, for each input character, the machine transitions to exactly one state.
• The uniqueness of computation is referred to as determinism.
• DFAs do not accept epsilon transitions.

Non-deterministic Finite Automata (NFA):

NFAs are capable of transitioning to any number of states for a particular input. They can accept epsilon transitions.

With Output Function FSM:

Moore Machine: Output function depends only on the state

Mealy Machine:Output function depends on the state and input symbol
Without Output function FSM (Semiautomatic or Transition System): DFA, NFA,$\epsilon$-NFA

Classification

• Acceptors: Indicate whether or not the received input is accepted
• Classifiers: Generalization of acceptors that produce n-ary output where n is strictly greater than two
• Transducers: Produce output based on given input.
• Sequencers(generators): Produce only a sequence as an output sequence of acceptor or transducer outputs

Pushdown Automata(PDA)

• A finite automata with extra memory called stack
• Stack help PDA to recognize Context Free Languages

New elements are pushed onto the stack.
These machines can do more than finite state machines but less than Turing machines.
There are two forms of PDA: “deterministic” and “non-deterministic,”

Extending PDA to allow a FSM to access two stacks to obtain a more powerful automaton equivalent to a TM

PDA components:

1. Input tape
2. Control unit
3. Stack with unlimited size

A PDA can be formally described as a 7-tuple $M = (Q, \Sigma, S, \delta, q_0, I, F)$, where:

• $Q$ : the finite set of states.
• $\Sigma$ : the input alphabet.
• $S$ : the stack alphabet.
• $\delta$ : the transition function: $Q \times (\Sigma \cup \{\varepsilon\}) \times S \rightarrow Q \times S^*$.
• $q_0$ : the initial state ($q_0 \in Q$).
• $I$ : the initial stack symbol ($I \in S$).
• $F$ : a set of accepting states ($F \subset Q$).

Linear-bounded Automata(LBA)

• A restricted type of TM.

• Its computation is limited to a finite bounded region.

• Can be used as acceptors for CSL. Similar to TM

• Characteristics:

  • Non-deterministic logic
  • Multiple tracks
  • Tape with finite length

An LBA can be formally described as an 8-tuple $M = (Q, T, E, q_0, ML, MR, S, F)$, where:

• $Q$ : the finite set of transition states.
• $T$ : the tape alphabet.
• $E$ : the input alphabet.
• $q_0$ : the initial state.
• $ML$ : the left boundary of the tape.
• $MR$ : the right boundary of the tape.
• $S$ : the transition function.
• $F$ : a finite set of final states.

Turning Machine

$f(s_1,a)=(s_2,A,R)$ $s_i$ : a state $A$: the replacement symbol $R(right)$: thr direction and control unit also can move $L(Left)$

1. The machine starts
2. Moves left or right replacing symbols as defined
3. Change the state as defined
4. Reach a halting state
5. The tape has changed from input to output

TM changes symbols on the tape and simulate the execution and storage of a computer.
Hence it could model all computations that can be computed by modern computers today.

The language consisting of strings accepted by a TM is called recursively enumerable language.

If the TM halts for every string, then the language is called recursive language.

Automata Theory (Chomsky hierarchy)

Grammar	Langugages	Automaton	Production Rules(Constraints)
Type-0	Recursively enumerable	Turing Machine	$\alpha \rightarrow \beta$
Type-1	Context-Sensitive	Linear-bounded non-deterministic Turning Machine	$\alpha A\beta \rightarrow \alpha \gamma \beta$
Type-2	Context-Free	Non-deterministic pushdown automaton	$A \rightarrow \gamma$
Type-3	Regular	Finite State Automaton	$A \rightarrow \alpha$ and $A \rightarrow \alpha B$