Strings and Languages
cs466(Prasad)
L2Lang
1
• Alphabet

• (Finite) set of atomic elements / letters
• String over

• Finite sequence of elements / letters from


  set of all stringsover
• Basis:
  
• Inductive step:
If     a   then a  
• Closure: …
cs466(Prasad)
L2Lang
2
• Language over 

is a subset of  .
• Examples
  {0,1}
  { , 0,1, 00,01,10,11, 000,001,...}
L1  {0,1}
L2  Bit st ringsending with 0
L3  Bit st ringsrepresentng
i opcodesfor a m/c
cs466(Prasad)
L2Lang
3
String Concatenation
string  string string
• Recursive Definition (cf. defn. of +)
• Signature:
u  u
concatenation
primitive operation
u( wa )  (uw)a
cs466(Prasad)
L2Lang
4
• String concatenation is associative.

u, v, w   : (uv)w  u(vw)
• Implication
– Order of performing concatenation is
immaterial.
– Parenthesis is redundant.
• Other Examples
– “+” and “*” on integers and matrices is
associative, while “-” on integers is not.
• Is NAND and NOR on booleans
associative?
cs466(Prasad)
L2Lang
5
• Refer to the text for the proof of
associativity of the concatenation operation.
• Refer to the text for the definition of reverse
of a string and its properties.
cs466(Prasad)
L2Lang
6
Descargar

Document