Lecture Notes for CS 373 - Theory of Computation with Viswanathan at Illinois (UIUC)

Notes Information

Material Type:Class Note
Class:CS 373 - Theory of Computation
Subject:Computer Science
University:University of Illinois - Urbana-Champaign
Term:Fall 2008
  • Buffer State
  • Either...or
  • Transitions
  • Immediately
  • Induction Step
  • Simple Solution
  • Language Definition
  • Proposition
  • Definitions
  • Normalization
Login / Sign Up to View Document
Preview Page 1Preview Page 2Preview Page 3Preview Page 4Preview Page 5Preview Page 6

Sample Document Text

CS 373: Theory of Computation Manoj Prabhakaran Mahesh Viswanathan Fall 2008 Part I Lecture 12 1 Context Free Grammars 1 Introduction Parenthesis Matching Problem Describe the the set of arithmetic expressions with correctly matched parenthesis. Arithmetic expressions with correctly matched parenthesis cannot be described by a regular expression . Let L be the language of correct expressions . Suppose h maps number and variables to epsilon1, and opening parenthesis to 0 and closing paren- thesis to 1 then h(L)?{0,1}? . h(L)?0?1? ={0n1n|n?0}which is not regular. This is an example of a context-free language, that we study. Parenthesis Matching Inductive Definition Ignoring numbers and variables, and focussing only on parenthesis, correctly matched expressions can be defined as . The epsilon1 is a valid expression . A valid string (negationslash= epsilon1) must either be - The concatenation of two correctly matched expressions, or - It must begin with ( and end with ) and moreover, once...

Related Documents

Complicated Notes
Autoeroticism Notes
Secondary Authority Notes
Definite Truth Values Notes
Impartiality Notes
Situation Questions Notes
Immediately Notes
Transitions Quiz
Informatica Notes
Either...or Exam
Coparenting Notes
Focus Group Research Notes
Critical Density Notes
Critical Density Notes
Somatic Mutations Notes
Somatic Mutations Notes
155, "/var/app/current/tmp/"