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

## Notes Information

 Material Type: Class Note Professor: Viswanathan Class: CS 373 - Theory of Computation Subject: Computer Science University: University of Illinois - Urbana-Champaign Term: Fall 2008 Keywords: Buffer StateEither...orTransitionsImmediatelyInduction StepSimple SolutionLanguage DefinitionPropositionDefinitionsNormalization

## 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