0.2.1.1. 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 set of strings, in particular, some subset of the powerset of \(\Sigma\).

0.2.1.2. 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, . . .\}\)

0.2.1.3. 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

Note: \(\rightarrow\), |, Variables vs. Terminals

0.2.1.4. Deriving a string¶

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

0.2.1.5. 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)^*\).

0.2.1.6. Example¶

0.2.1.7. .¶

.

0.2.1.8. 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) =\) ?

0.2.1.9. Another Grammar Example¶

\(G=(\{S, B\}, \{a\}, S, P)\)

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

\(L(G) =\) ?

0.2.1.10. Key Concept: Automata¶

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