Problem Solving

Problem Solving

1. Grammars

   • Languages
     • Natural Language
       • This is a language for speech. There are rules, grammar and spelling but they can be broken.
     • Formal Language
       • This is a language written for a specific purpose - to describe something, classification or for giving instructions. There is an alphabet and an agreed list of words. EG. pencils allow H, B, HB, 2B, 3B, 4B, 2H, 3H and 4H only
     • Regular Language
       • This is a language that can be expressed as a FSM. This has an alphabet and a set list of strings. They can specify patterns, eg. determine the pattern an email address can take
   • Metacharacters
     • |
       • Vertical bar separates alternatives. a|b can be a or b 
     • ?
       • Indicates there is zero or one of the preceding element. colou?r matches colour or color
     • *
       • Indicates zero or more of the preceding element. ab*c matches ac, abc, abbc, abbbc etc.
     • +
       • indicates one or more of the preceding element. ab+c matches abc, abbc but not ac
     • ()
       • round brackets are for grouping. (ac)* matches ac, acac, acacac
     • []
       • square brackets are another way of expressing alternatives but can be used for ranes too [ab] matches a or b 
     • \
       • backslash. the subsequent character is to be treated literal.
     • ^
       • Used to match the beginning of a string. 
     • [^]
       • subsequent character is neglected. n[^t] means n followed by any character but a t
     • $
       • Match the end of a string
     • .
       • matches a single character, can be any.eg. .an can be can, fan, tan etc.
     • [-]
       • indicates a range in class. eg  [a-z] matces all letters from a to z

2. Finite state machines

   • Backus -Naur form