Languages and computational problems covered in COSC341 lectures and tutorials

L1
* Two buttons one light
* Both switches must be in odd parity for light to be on (DFA)
* Zero or more copies of a followed by exactly one b (DFA)

L4
* Words over Sigma = {a} such that the number of letters is a multiple of 2 or one more than a multiple of three (NFA)

T4
* EVEN
* Has-abba
* Even-Even
* Multi-6-b

T5
* Strings of a's and b's with either no pair of consecutive b’s or no pair of consecutive a’s.

T6
* Palindromes (Not regular)

L6
* {a^n b^n : n >= 0} - not regular (Myhill-Nerode). L9 shows a PDA for it (so it's context-free)

L9
{a^n b^n c^t n,t >= 0} - context free
{a^s b^n c^n n,t >= 0} - context free
{a^n b^n c^n n >= 0} - NOT context free (via pumping lemma)
POWERS-OF-2 - NOT context free (via pumping lemma)

L10 (TMs)
* POWERS-OF-2
* w#w for w in {a,b}*

T9&10
* Equal: same number of a's and b's in any order - created a PDA (see notes made live on my tablet) and a CFG.
* {a^n b^n c^m : n,m >= 0} - PDA and CFG
* BalancedParentheses - PDA and CFG
* PostFix - PDA and CFG
* {a^n b^m a^n b^m : n,m >= 0} - NOT context-free (pumping lemma)
* {a^p : p is prime} - NOT context-free (pumping lemma)
* {a^n b^n a^n : n >= 0} - NOT context-free (pumping lemma)

L14 
HALT (more in L15)

L15
Blank-Halt

L16 and onwards not yet included