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> \(\rightarrow\) <subject><verb><d.o.>
<subject> \(\rightarrow\) <noun> | <article><noun>
<verb> \(\rightarrow\) hit | ran | ate
<d.o.> \(\rightarrow\) <article><noun> | <noun>
<noun> \(\rightarrow\) Fritz | ball
<article> \(\rightarrow\) 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 \in 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 \Rightarrow z: \qquad w\) derives \(z\)
\(w \stackrel{*}{\Rightarrow} z: \qquad\) derives in 0 or more steps
\(w \stackrel{+}{\Rightarrow} z: \qquad\) 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 \rightarrow aaS, S \rightarrow b\}\)
\(L(G) =\) ?

Another Grammar Example

\(G=(\{S, B\}, \{a\}, S, P)\)
\(P=\{S \rightarrow a \mid aB, B \rightarrow aa \mid aaB\}\)
\(L(G) =\) ?

Key Concept: Automata

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