CSIR Study Materials   UGC NET SLET Exam   PMT Examination   Study in USA

State Level Eligibility Test

PAPER-III(B)
[ELECTIVE / OPTIONAL ]

Elective—I
Theory of Computation : Formal language Need for formal computational models. Noncomputational problems, diagonal argument and Russel’s paradox.

Deterministic Finite Automaton (DFA), Non-deterministic Finite Automaton (NFA), Regular languages and regular sets. Equivalence of DFA and NFA. Minimizing the number of states of a DFA. Non-regular languages, and Pumping lemma.

Pushdown Automaton (PDA), Deterministic Pushdown Automaton (DPDA), Nonequivalence of PDA and DPDA.

Context free Grammars : Grelbach Normal Form (GNF) and Chomsky Normal Form (CNF), Ambiguity. Parse Tree Representation of Derivations. Equivalence of PDA’s and CFG’s.

Parsing techniques for parsing of general CFG’s—Early’s, Cook-KassamI-Younger (CKY), and Tomlta’s parsing.

Linear Bounded Automata (LBA) : Power of LBA. Closure properties. Turing Machine (TM) : One tape, multitape. The notions of time and space complexity in terms of TM. Construction of TM for simple problems. Computational complexity. Chomsky Hierarchy of languages : Recursive and recursively-enumerable languages.

Elective—II
Models for Information Channel : Discrete Memoryless Channel, Binary Symmetric Channel (BSC), Burst Channel, Bit-error rates. Probability, Entropy and Shannon’s measure of Information. Mutual Information. Channel capacity theorem. Rate and optimality of Information transmission. Variable Length Codes: Prefix Codes, Huffmann Codes, Lempel-Ziev (LZ) Codes.

Optimality of these codes. Information content of these codes. Error Correcting and Detecting Codes : Finite fields, Hamming distance. Bounds of codes, Linear (Parity Check) codes. Parity check matrix. Generator matrix, Decoding of linear codes, Hamming codes. Image Processing : Image Registration, Spatial Fourier Transforms, Discrete Spatial (2-dlmenslonal) Fourier Transforms, Restoration, Lossy Compression of images (pictures).

Data Compression Techniques: Representation and compression of text, sound, picture, and video files (based on the JPEG and MPEG standards).