Close
Close Window

| About   «  0.1. Formal Languages Course Introduction   ::   Contents   ::   0.3. Deterministic Finite Acceptors  »

0.2. Key Concepts

0.2.1. Key Concepts

0.2.1.1. Key Concept: Language

  • Σ: 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 Σ

So, a language is a set of strings, in particular, some subset of the powerset of Σ.

0.2.1.2. Language Examples

  • Σ={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,...}
  • Σ={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.
  • Σ={a,b}
    L={anbn|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> <subject><verb><d.o.>
<subject> <noun> | <article><noun>
<verb> hit | ran | ate
<d.o.> <article><noun> | <noun>
<noun> Fritz | ball
<article> the | an | a

Note: , |, 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 (SV).
P is a set of productions (rules).

xy means to replace x by y.

Here, x(VT)+,y(VT).

0.2.1.6. Example

0.2.1.7. .

.

0.2.1.8. Grammar Notation

wz:w derives z
wz: derives in 0 or more steps
w+z: derives in 1 or more steps
Given grammar G=(V,T,S,P), define
L(G)={wTSw}
Example
G=({S},{a,b},S,P)
P={SaaS,Sb}
L(G)= ?

0.2.1.9. Another Grammar Example

G=({S,B},{a},S,P)
P={SaaB,BaaaaB}
L(G)= ?

0.2.1.10. Key Concept: Automata

Created with Raphaël 2.1.2
  1. a
  2. a
  3. b
  4. b
  5. a
  6. b
input tape
tape head
control unit
0
1
storage
(optional)

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

   «  0.1. Formal Languages Course Introduction   ::   Contents   ::   0.3. Deterministic Finite Acceptors  »

Close Window