Skip to main content

Print this page

Catalog Search

Search Options

Contents

About
University Policies
Undergraduate Programs
Graduate Programs
Benjamin N. Cardozo School of Law
College of Dental Medicine
Pathways Programs
Partnerships with Other Universities
Courses
- ACC - Accounting
- AIM - Artificial Intelligence & Machine Learning
- AIM Artificial Intelligence and Machine Learning
- ART - Art (UM)
- ARTS - Art (UW)
- BBLE - Bible (UW)
- BIB - Bible (UM & GR)
- BIBL - Bible (UW & GR)
- BIMS - Biomedical Science
- BIO - Biology (UM)
- BIOE - Bioethics
- BIOL - Biology (UW)
- BLW - Business Law
- BTM - Biotechnology Management
- BUS - Business & Management
- CHE - Chemistry (UM)
- CHEM - Chemistry (UW)
- COM - Computer Science (UM & GR)
  - 1000-level
  - 2000-level
  - 3000-level
  - 4000-level
  - 5000-level
  - 6000-level
  - 7000-level
- COMP - Computer Science (UW)
- CSD - Communication Sciences & Disorders
- CYB - Cybersecurity
- DAV - Data Analytics & Visualization
- DENT Dentistry
- ECO - Economics (UM)
- ECON - Economics (UW)
- EDU - Education
- EDUC - Education (UW)
- EEX - Exceptional Education
- ENG - English (UM)
- ENGL - English (UW)
- ENT - Entrepreneurship
- FIN - Finance
- FNL Foreign Language (UM)
- FNLG Foreign Language (UW)
- FYS - First Year Seminar
- FYSM - First Year Seminar
- FYSW - First Year Seminar
- FYWR - First Year Writing
- HAL - Halakhah (UM & RIETS)
- HEB - Hebrew (UM & GR)
- HEBR - Hebrew (UW)
- HES - Hebrew Studies (UM)
- HIS - History (UM)
- HIST - History (UW)
- HLTH - Health
- HOL - Holocaust and Genocide Studies
- HON - Honors (UM)
- HONR - Honors (UW)
- HUM - Humanities
- IDS - Information & Decision Science
- INDS - Interdisciplinary Studies (UW)
- INF - Information Systems
- JED - Jewish Education (UM)
- JEDU - Jewish Education (UW)
- JHI - Jewish History (UM & GR)
- JHIS - Jewish History (UW)
- JPH - Jewish Philosophy (UM & GR)
- JPHI - Jewish Philosophy (UW)
- JPHL - Jewish Philosophy (UW)
- JST - Jewish Studies (UM & GR)
- JTH - Jewish Thought (UM)
- JTP - Jewish Thought and Philosophy (UM & GR)
- JUD - Judaic Studies (UM)
- JUDS - Judaic Studies (UW)
- LAW - Law
- MAN - Management
- MANA - IP: Management
- MAR - Marketing
- MAT - Mathematics (UM & GR)
- MATH - Mathematics (UW)
- MGMT - Management
- MUS - Music (UM)
- MUSI - Music (UW)
- NES - Near Eastern Studies (UM)
- NUR - Nursing
- OTH - Occupational Therapy
- PAS - Physician Assistant Studies
- PFM - Psychology - Family & Marriage
- PHI - Philosophy (UM)
- PHIL - Philosophy (UW)
- PHY - Physics (UM & GR)
- PHYS - Physics (UW)
- POL - Political Science (UM)
- POLI - Political Science (UW)
- PSA - General Psychology
- PSC - Clinical Psychology
- PSH - Clinical Health Psychology
- PSM - Applied Psychology
- PSS - School Psychology
- PSY - Psychology (UM)
- PSYC - Psychology (UW)
- PUB - Public Health (UW)
- RE - Real Estate
- REA - Real Estate
- SCIE Science UW
- SEM Semitic Languages (UM)
- SEMI - Semitic Languages (UW)
- SOC - Sociology (UM)
- SOCI - Sociology (UW)
- SPAU - Speech Pathology and Audiology (UW)
- SPE Speech UM
- SPEE - Speech (UW)
- STA - Statistics (UM)
- STAT - Statistics (UW)
- SWK - Social Work
- TAL - Talmud (UM & GR)
- TALS - Talmudic Studies (GR W)
- TAN - Tanakh (UM)
- TAS - Talmudic Studies (GR)
- TAX - Tax
- THEA - Theater Arts (UW)
- TMG - Technology Management
- WMNS - Women's Studies (UW)
Administration
Research
Student Affairs
Jewish Life
Graduate Admissions
Undergraduate Admissions
Tuition and Financial Aid
Athletics
Resources and Services
Campus Safety
Campus Maps
Contact Us
Support YU
Compliance Information
Disclaimer

Catalog Links

COM 1621 Theory of Computation

Deterministic and nondeterministic finite state automata; regular grammars and regular expressions; equivalence of regular expressions and finite automata; pumping lemma for regular languages; context free grammars; languages generated by context free grammars; parse trees and ambiguity; Chomsky normal form; pushdown automata; equivalence of context free grammars and pushdown automata; pumping lemma for context free languages; Turing machines; Universal Turing machine; Halting problem; solvable and unsolvable problems about automata and languages; introduction to complexity theory; NP-complete problems.

Credits

3