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 | aNote: →, |, 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 ballCan 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) whereV 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→y means to replace x by y.
Here, x∈(V∪T)+,y∈(V∪T)∗.
0.2.1.6. Example¶
0.2.1.7. .¶
.
0.2.1.8. Grammar Notation¶
w⇒z:w derives zw∗⇒z: derives in 0 or more stepsw+⇒z: derives in 1 or more stepsGiven grammar G=(V,T,S,P), defineL(G)={w∈T∗∣S∗⇒w}ExampleG=({S},{a,b},S,P)P={S→aaS,S→b}L(G)= ?
0.2.1.9. Another Grammar Example¶
G=({S,B},{a},S,P)P={S→a∣aB,B→aa∣aaB}L(G)= ?
0.2.1.10. Key Concept: Automata¶
- a
- a
- b
- b
- a
- b
input tapetape headcontrol unit01storage(optional)Numbers in control unit symbolize “states”, which are the specific positions on the dial that the arrow can point to.