COMP 335 Lecture Notes - Lecture 3: Tape Head, Control Unit, Substring
Document Summary
L = {a2i | i >= 0 } Because l is an even length string and concatenating it with another even length string will always give you an even length string. L+ = l u l2 u l3 u = l. Now looking at the definition of the a sentence we can construct: A grammar can be concise way of specifying a language. A grammar has rules with which we can generate valid sentences. A grammar is a quadruple g = (v,t,s,p) where. T is a finite set of terminal symbols (alphabet) P is a finite set of productions (rules) of the type. X => (cid:455) (cid:449)here (cid:454) (cid:894)v u t(cid:895)+ and (cid:455) (cid:894)v u t(cid:895)* We can repeatedly apply productions of the grammar, w => w1 = w2 => wn, we say w *=> wn w derives wn in zero or more steps. Strings of terminals that we can derive with this: