## Notes Information

Login / Sign Up to View Document

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

© Copyright 2020 , Koofers, Inc. All rights reserved.

The information provided on this site is protected by U.S. and International copyright law, and other applicable intellectual property laws, including laws covering data access and data compilations. This information is provided exclusively for the personal and academic use of students, instructors and other university personnel. Use of this information for any commercial purpose, or by any commercial entity, is expressly prohibited. This information may not, under any circumstances, be copied, modified, reused, or incorporated into any derivative works or compilations, without the prior written approval of Koofers, Inc.