0.Key Concept: Language§

$\Sigma$ : A set of symbols, an alphabet
- Notation: Usually we use for examples: $a, b, c$
String: Finite sequence of symbols (from some alphabet)
- Notation: usually we use for exampls: $u, v, w$
Language: A subset of the strings defined over $\Sigma$

So, a language is a sets of strings, in particular, some subset of the powerset of $\Sigma$ .

Language Examples

$\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$

$L = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ... \}$
$\Sigma = \{a, b, c\}$

$L = \{ab, ac, cabb\}$

$L$ is a language with 3 strings, each string is a sequence of strings formed over the alphabet.
$\Sigma = \{a, b\}$

$L = \{a^n b^n | n > 0\}$

This is an example of an infinite language.

What are the strings in the language? $\{ab, aabb, aaabbb, aaaabbbb, . . .\}$

Key Concept: Grammars

A tiny subset of the english language, not complete!

<sentence> → <subject><verb><d.o.>
<subject> → <noun> | <article><noun>
<verb> → hit | ran | ate
<d.o.> → <article><noun> | <noun>
<noun> → Fritz | ball
<article> → the | an | a

Variables vs. Terminals

Deriving a sentence

A variable in the grammar can be replaced by the right hand side of its rule:

Fritz hit the ball

<sentence> -> <subject><verb><d.o>
           -> <noun><verb><d.o>
           -> Fritz <verb><d.o.>
           -> Fritz hit <d.o.>
           -> Fritz hit <article><noun>
           -> Fritz hit the <noun>
           -> Fritz hit the ball

Can we derive these sentences? If not, can we change the grammar?:

The ball hit Fritz

The ball ate the ball

Formal definition of a grammar

A grammar

$G = (V, T, S, P)$ where

V is a finite set of variables (nonterminals).
T is a finite set of terminals (generally, these are strings).
S is the start variable (S∈V).
P is a set of productions (rules).

$x \rightarrow y$ means to replace $x$ by $y$ .

Here, $x \in (V \cup T)^+, y \in (V \cup T)^*$ .

Example

.

Grammar Notation

w⇒z:w derives z
w∗⇒z: derives in 0 or more steps
w+⇒z: derives in 1 or more steps

Given grammar

$G = (V, T, S, P)$ , define

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

Example

G=({S},{a,b},S,P)
P={S→aaS,S→b}
L(G)= ?

Another Grammar Example

G=({S,B},{a},S,P)
P={S→a∣aB,B→aa∣aaB}
L(G)= ?

Key Concept: Automata

input tape

tape head

control unit

storage

(optional)

Numbers in control unit symbolize “states”, which are the specific positions on the dial that the arrow may point to.