CSE 224 Lesson 1

CS 322 / CSE 224  «   AUTOMATA AND LANGUAGE THEORY

     R ₁  Rich, Elaine ( 2009 ) . Automata, Computability and Complexity. New Jersey : Pearson Prentice Hall

     R ₂  Cohen, Daniel I. A. ( 1991 ) . Introduction to Computer Theory  . New York : John Wiley and Sons

    R ₃  Brookshear, J. Glenn . ( 1989 ) Theory of Computation, Formal languages, Automata, and Complexity . Redwood City,

                     California : The Benjamin / Cummings Publishing Company Inc. 1989

      R ₄  Kolman, Bernard ; Busby, Robert and Ross, Sharon Cutler ( 2000 ). Discrete Mathematical  Structures 4^th ed  .

                    New Jersey  :  Prentice – Hall Inc. 

       Automata Theory, concept that describes how machines mimic human behavior. The theory proposes that human physical functions and behavior can be simulated by a mechanical or computer-controlled device. Applications of automata theory have included imitating human comprehension and reasoning skills using computer programs, duplicating the function of muscles and tendons by hydraulic systems or electric motors, and reproducing sensory organs by electronic sensors such as smoke detectors.

       The concept of automata, or manlike machines, has historically been associated with any self-operating machine, such as watches or clockwork songbirds driven by tiny springs and gears. But in the late 20th century, the science of robotics (the development of computer-controlled devices that move and manipulate objects) has replaced automata as it relates to replicating motion based on human anatomy (see Robot). Modern theories of automata currently focus on reproducing human thought patterns and problem-solving abilities using artificial intelligence and other advanced computer-science techniques.

BRIEF HISTORY

       Automata date to ancient times. During the Han dynasty (3rd century BC), a mechanical orchestra was constructed for the Chinese Emperor. The 13th-century English philosopher and scientist Roger Bacon is credited with creating an artificial talking head, and in the 17th century French philosopher and mathematician René Descartes reportedly built a female automaton as a traveling companion. In the 18th and 19th centuries, intricate machines were constructed that imitated some human actions, such as limb movement, but these devices were little more than sophisticated windup toys. Mimicry of human mental abilities did not begin until the advent of electronics and mathematical logic structures. In the mid-20th century, the British mathematician Alan Turing designed a theoretical machine to process equations without human direction. The machine (now known as a Turing machine), in concept resembled an automatic typewriter that used symbols for math and logic instead of letters. Turing intended the device to be used as a “universal machine” that could be programmed to duplicate the function of any other existing machine. Turing's machine was the theoretical precursor to the modern digital computer.

       In the 1940s and 1950s American researchers Warren McCulloch and Walter Pitts at the Massachusetts Institute of Technology developed artificial neurons, or neural networks, to theoretically bridge the structure of the human brain and the still-to-be-invented modern computer. The human brain has about 1 trillion nerve cells, or neurons, each of which is connected to several other neurons. This allows neurons to transmit information along different pathways, depending on the stimulation they receive. McCulloch and Pitts theorized that this same mode of information transmission, an interconnected network, might be reproduced with electronic components. Artificial neural networks have been shown to have the capacity to learn from their experiences and enhance their computational performance.

       In 1956 American social scientist and Nobel laureate Herbert Simon and American physicist and computer scientist Allan Newell at Carnegie Mellon University in Pennsylvania devised a program called Logic Theorist that simulated human thinking on computers, although at first the program was simply written on index cards due to the scarcity of computers. Newell and Simon later created a modified version of the program called the General Problem Solver (GPS). The GPS was unique in that it was programmed to achieve a goal and then find the means to reach that goal—as opposed to starting from a problem or question and working toward an eventual solution. The GPS process involved backward thinking, going from the final solution to the present state. Using computers from the Rand Corporation to test GPS, Simon and Newell found that in some cases GPS did act as if it were capable of human reasoning. This was one of the first breakthroughs in the computer-science field that would later be known as artificial intelligence.

            The first artificial intelligence conference occurred at Dartmouth College in New Hampshire in 1956. This conference inspired researchers to undertake projects that emulated human behavior in the areas of reasoning, language comprehension, and communications. In addition to Newell and Simon, computer scientists and mathematicians Claude Shannon, Marvin Minsky, and John McCarthy laid the groundwork for creating “thinking” machines from computers. Contemporary fields of interest resulting from early artificial intelligence research include expert systems, cellular automata, and artificial life.

 

CHAPTER  1  *   INTRODUCTION

            The 20^th century has been filled with the most incredible shocks and surprises : theory of relativity, Communist revolutions, psychoanalysis, nuclear war, television, moon walks, genetic engineering, etc. As astounding as any of these is the advent of the computer and its development from a mere calculating device into what seems like a “thinking machine”. We are not after the history computers but the we are concerned with the theory of computers, which means that we form several abstract mathematical models that will describe with varying degrees of accuracy parts of computers and types of computers and similar machines.

       There are separate courses that deal with circuits and switching theory  (computer logic) and with instruction sets and register arrangements ( computer architecture) and with data structures and algorithms, operating systems, compiler design and artificial intelligence and etc. All these courses have theoretical component, but they differ from our study in two aspects :

           1.  They deal with computers that already exist;   

           2.  They are interested in how best to do things

     The history of computer theory is also interesting which was formed by fortunate coincidences, involving seemingly unrelated branches of intellectual endeavor. The most obvious component of computer theory is the theory of mathematical logic.

      Georg Cantor ( 1845 – 1918 ) invented the theory of sets, but at the same time he had discovered some very uncomfortable paradoxes – he created things that look like contradiction in what seemed to be rigorously proven mathematical theorems. Some of his unusual findings could be tolerated ( such as that infinity comes in different sizes ) but some could not ( such as that some set is bigger is bigger than the universal set). This left a cloud over mathematics that needed to be resolved.

       David Hilbert ( 1862 – 1943 ) – wanted all of mathematics put on the same sound footing as Euclidean geometry, which is characterized by precise definitions, explicit axioms, and rigorous proofs. He believed that if mathematics were put back on the Euclidean standard the cantor paradoxes would go away. He was actually concerned with two ambitious projects :

           1.  To demonstrate that the new system was free of paradoxes;

           2.  To find methods that would guarantee to enable humans to construct proofs of all the  

                 true statements in mathematics.

            This type of complete, guaranteed, easy-to-follow set of instructions is called algorithm. Hilbert hoped that algorithms or procedures could be developed to solve whole classes of mathematical problems. Mathematical logicians while trying to follow the suggestions of Hilbert and straighten out the predicament left by Cantor, found that they were able to prove mathematically that some of the desired algorithms cannot exists – not only at this time, but they can never exist in the future.

         Kurt Godel ( 1906 – 1978 ) not only showed that there was no algorithm  that could guarantee to provide proofs for all the true statements in mathematics, but he proved that not all the true statements even have a proof to be found. Godel’s Incompleteness Theorem implies that in a specific mathematical system either there are some true statements without any possible proof or else there are some false statements that can be “proven.”

         Alonzo Church proposed the first general definition of an algorithm. Using his definition and together with

 Stephen Cole Kleene, and independently Emil Post they were able to prove that there were problems that no algorithm could solve. 

                        Alan Mathison Turing (1912-1954), British mathematician, who did pioneering work in computer theory. He was born in London and educated at Cambridge and Princeton universities. In 1936, while he was still a graduate student, Turing published a paper called “On Computable Numbers,” which introduced the concept of a theoretical computing device now known as a Turing machine. The concept of this machine, which could theoretically perform any mathematical calculation, was important in the development of the digital computer. Turing also extended his mathematical work to the study of artificial intelligence and biological forms. He proposed a method called the Turing test, to determine whether machines could have the ability to think. During World War II (1939-1945), Turing worked as a cryptographer for the British Foreign Office. In 1951 Turing was named a Fellow of the Royal Society and in 1952 he began to publish his work on the mathematical aspects of pattern and form development in living organisms. He apparently committed suicide in 1954 , probably in reaction to medical treatments he was forced to receive in order to “cure” him of homosexuality.

            Turing develop the concept of a theoretical “universal algorithm machine.” Studying what was possible and what was not possible for such a machine to do, he discovered that some task that we might have expected this abstract omnipotent machine to be able to perform are impossible, even for it. Turing’s model for a universal algorithm machine is directly connected to the invention of the computer. In fact for a completely different reason, Turing himself had an important part in the construction of the first computer, which he based on his work in abstract logic.

             Sturgis McCulloch and Walter Pitts ( 1923 – 1969 ) constructed a mathematical model for the way in which sensory receptor organs in animal behave. The model they constructed for a “neural net” was a theoretical machine of the same nature as the one Turing invented, but with certain limitations.

The invention of the vacuum tube and the development in electronics enabled engineers to build fully automatic  electronic calculators. These development fulfilled the age-old dream of Blaise Pascal (1623 – 1662),  Gottfried      

Wilhelm von Leibniz (1646 – 1716 ) an Charles Babbage (1792 – 1871), all of whom built mechanical calculating devices as powerful as their respective technologies would allow.

            The First Generation Computers – built in the 1940’s :

                        1.  The Computer Colossus at Bletchley, England ( Turing’ decoder )

                        2.  The ABC Machine built by John Atanosoff in Iowa

                        3.  Harvard Mark I built by Howard Aiken,

                        4.  ENIAC, built by John Presper Eckert Jr. and John William Mauchly ( 1907–1980 )

                                    at the University of Pennsylvania.

            John von Neumann (1903 – 1957 ) – developed the idea of a stored-program computer. The idea of storing the program inside the computer and allowing the computer to operate on ( and modify ) the program as well as the data was a tremendous advance. This may also been conceived earlier by Babbage and his co-worker Ada Augusta, Countess of Lovelace ( 1815 – 1853 ) but their technology was inadequate to explore this possibility.

Von Neumann’s goal was to convert the electronic calculator into a real – life model of one of the logician’s ideal universal algorithm machines, such as those Turing had described.  Along with the concept of programming a computer came the question : What is the best language in which to write programs.

            Noam Chomsky created the subject of mathematical models for the description of languages to answer these questions. His theory grew to the point where it began to shed light on the study of computer languages.  The formulation of mathematical logic became useful to linguistics , a previously nonmathematical subject. Metaphorically, we could say that the computer then took on linguistic abilities.  It became a word processor, a translator, and an interpreter of simple grammar, as well as a compiler of computer languages. The software invented to interpret programming languages was applied to human languages as well.

            One point that will be made clear in the study is why computer languages are easy for a computer to understand whereas human languages are very difficult.

AUTOMATA THEORY

            Automata is defined as a system where energy, information and material is transformed, transmitted and used for performing some function without the direct participation of man . In theoretical computer science, automata theory is the study of abstract machines and problems they are able to solve. Automata theory is closely related to formal language theory as the automata are often classified by the class of formal languages they are able to recognize.

            An automaton is a mathematical model for a finite state machine (FSM). A FSM is a machine that, given an input of symbols, "jumps" through a series of states according to a transition function (which can be expressed as a table). In the common "Mealy" variety of FSMs, this transition function tells the automaton which state to go to next given a current state and a current symbol.

            The input is read symbol by symbol, until it is consumed completely (think of it as a tape with a word written on it, that is read by a reading head of the automaton; the head moves forward over the tape, reading one symbol at a time). Once the input is depleted, the automaton is said to have stopped.

Depending on the state in which the automaton stops, it's said that the automaton either accepts or rejects the input. If it landed in an accept state, then the automaton accepts the word. If, on the other hand, it lands on a reject state, the word is rejected. The set of all the words accepted by an automaton is called the language accepted by the automaton.

            Note, however, that, in general, an automaton need not have a finite number of states, or even a countable number of states. Thus, for example, the quantum finite automaton has an uncountable infinity of states, as the set of all possible states is the set of all points in complex projective space. Thus, quantum finite automata, as well as finite state machines, are special cases of a more general idea, that of a topological automaton, where the set of states is a topological space, and the state transition functions are taken from the set of all possible functions on the space. Topological automata are often called M-automata, and are simply the augmentation of a semiautomaton with a set of accept states, where set intersection determines whether the initial state is accepted or rejected.

            In general, an automaton need not strictly accept or reject an input; it may accept it with some probability between zero and one. Again this is illustrated by the quantum finite automaton, which only accepts input with some probability. This idea is again a special case of a more general notion, the geometric automaton or metric automaton, where the set of states is a metric space, and a language is accepted by the automaton if the distance between the initial point, and the set of accept states is sufficiently small with respect to the metric.

CHAPTER  2   *   LANGUAGES

            In English we distinguish the three different entities: letters, words and sentences. There is a certain parallelism between the fact that group of letters make up words and the fact that group of words make up sentences. Not all collection of letters form a valid word, and not all collection of words form a valid sentences. The analogy can be continued. Certain groups of sentences make up coherent paragraphs, certain groups of paragraphs make up coherent stories and so on.

             The same situation  also exist with computer language. Certain character strings are recognizable words

( GOTO, END. ) Certain string of words are recognizable commands. Certain sets of commands  become a program (with or without data). To construct a general theory that unifies all these examples, it is necessary to adopt a definition of a most “universal language structure”, that is, a structure in which the decision of whether a given string of units constitutes a valid larger unit is not a matter of guess work but is based on explicitly stated rules. It is very hard to state all the rules for the language “spoken English”, since many seemingly incoherent strings of words are actually understandable utterances. This is due to slang, idiom, dialect, and our ability to interpret poetic metaphor and to correct unintentional grammatical errors in the sentences we hear.      Language will be considered solely as symbols on paper and not as expression of ideas in the minds of humans.  In this basic model, language is not communication among intellects, but a game of symbols with formal

rules. The term formal emphasizes that it is the form of the string of symbols we are interested in, and not the meaning.

            Automata plays a major role in compiler design and parsing. The basic concepts of  symbols, words, alphabets and strings  are common to most descriptions of automata. These are the following :

            Symbol An arbitrary datum which has some meaning to or effect on the machine. Symbols are sometimes just called "letters".

Kleene closure  A language may be thought of as a subset of all possible words. The set of all possible words may, in turn, be thought of as the set of all possible concatenations of strings. Formally, this set of all possible strings is called a free monoid. It is denoted as Σ ^*, and the superscript * is called the Kleene star.

            Alphabet  is a finite set of symbols out of which we build structures. An alphabet is denoted by Σ, which is the set of letters in an alphabet.

            Language  is a specified set of strings of characters, formed by symbols in a given alphabet. May or may not be infinite. Word   is a finite string formed by the concatenation of a number of symbols. Words are those strings that are permissible in the language.

            Empty or null string is a string that has no letters and is denoted by the symbol  L.  No matter what language is considered, the null string is always  L. Two words are considered the same if all their letters are the same and in the same order  so there is only one possible word of no letters. For clarity, we do not allow the symbol L to be part of the alphabet for any language.

            There is a difference between the word that has no letters L and the language that has no words. The null set Æ is use to denote the language that has no words. It is not true that  L is a word in the language Æ since this language has no words at all. If a language  L does not contain the word L and we wish to add it to L, we use the “union of sets” operation denoted by “+” to form  L  + { L }. This language is not the same as L, however  L +  Æ is the same as L because there is no new word that has been added.

Formal  Language

A formal language is a set of words, i.e. finite strings of letters, or symbols. The inventory from which these letters are taken is called the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar. Formal languages are a purely syntactical notion, so there is not necessarily any meaning associated with them. To distinguish the words that belong to a language from arbitrary words over its alphabet, the former are sometimes called well-formed words (or, in their application in logic, well-formed formulas).

Formal languages are studied in the fields of logic, computer science and linguistics. Their most important practical application is for the precise definition of syntactically correct programs for a programming language. The branch of mathematics and computer science that is concerned only with the purely syntactical aspects of such languages, i.e. their internal structural patterns, is known as formal language theory.

Although it is not formally part of the language, the words of a formal language often have a semantical dimension as well. In practice this is always tied very closely to the structure of the language, and a formal grammar (a set of formation rules that recursively defines the language) can help to deal with the meaning of (well-formed) words. Well-known examples for this are "Tarski's definition of truth" in terms of a T-schema for first-order logic, and compiler generators like lex and yacc.

Words over an alphabet

          An alphabet, in the context of formal languages can be any set, although it often makes sense to use an alphabet in the usual sense of the word, or more generally a character set such as ASCII. Alphabets can also be infinite; e.g. first-order logic is often expressed using an alphabet which, besides symbols such as  Ù ,  Ø , "  and parentheses, contains infinitely many elements x₀, x₁, x₂, … that play the role of variables. The elements of an alphabet are called its letters.

         A word over an alphabet can be any finite sequence, or string, of letters. The set of all words over an alphabet Σ is usually denoted by Σ^* (using the Kleene star). For any alphabet there is only one word of length 0, the empty word, which is often denoted by e, io9ε or Λ. By concatenation one can combine two words to form a new word, whose length is the sum of the lengths of the original words.   The result of  concatenating a word with the empty word is the original word. In some applications, especially in logic, the alphabet is also known as the vocabulary and words are known as formulas or sentences; this breaks the letter/word metaphor and replaces it by a word/sentence metaphor.

English is the most familiar example of a language. The alphabet is the usual set of letters plus the apostrophe and hyphen and is denoted by the Greek upper case letter sigma, S.

                        S = {  a   b   c   d   e   . . .   z    ‘    -  } 

  

            Upper case letters are also included in S.  We can now specify which strings of these letters are valid words in the language by listing them all, as is done in a dictionary. If we call this language as ENGLISH-WORDS, then

            ENGLISH-WORDS = { all the words ( main entries ) in a standard dictionary }

   If   G ( capital letter gamma ) make a formal definition of the language of the sentences in English, then, our alphabet is the entries in the dictionary.

                        G = { the entries in a dictionary, plus a blank space, plus the usual punctuation marks }

            In general, the abstract languages treated will be defined in one of two ways. Either they will be presented as an alphabet and the exhaustive list of all valid words, or else they will be presented as an alphabet and a set of rules defining the acceptable words. Earlier , it was mentioned that a language can be defined by presenting the alphabet and then specifying which strings are words. The word “specify” is trickier than we may at first supposed.

Consider the example of the language MY-PET.  The alphabet of this language is { a  c  d  g  o  t }. The possible words are : MY-PET = {cat, dog, goat, toad }.

                                               

            Consider an alphabet having only one letter, the letter x ;    S = { x },

         we can define a language by saying that any nonempty string of alphabet character is a word.  

                 L₁ = { x  xx   xxx  xxxx  xxxxx  . . . }  or alternately     L₁ = { xⁿ  for  n  =  1   2   3 . . . }

Because of the way we define it, this language does not include the null string.

           Concatenation is an operation wherein two strings are written down side by side to form a new longer string. If  xx is concatenated with xxxx , xxxxxx is formed. The words in this language are clearly analogous to the positive integers, and the operation of concatenation is analogous to addition.

                      If  xⁿ  is concatenated with  x^m , the word is  x^{n + m}.  

            If  a = xx  and  b =  xxx,  then if a is concatenated with b ð  ab = xxxxx.

   

It is not always true that when two words are concatenated they produce another word in the language. For example if the language is :

            L₂ = { x  xxx  xxxxx  xxxxxxx . . . }  =  { x^odd } =  { x^{2n + 1}  for  n  =  0   1   2   3  . . . }

            a = xxx ,  b =  xxxxx  are both words in L₂  but their concatenation  ab  =  xxxxxxxx  is not in L₂.

In the examples,  when we concatenate a with b we get the same result when we concatenate b with a.

            Thus, ab = ba , but this does not hold for all languages. In English when we concatenate  “house”  and “fly” we get “housefly” which is a word but distinct from “flyhouse”, which is a different thing  -- not because they have different meanings but because they are different words. 

            Consider another language. Let us begin with the alphabet  S = { 0  1  2  3  4  5  6  7  8  9 } and define the set of words : L₃ = { any finite string of alphabet letters that does not start with the letter 0 }. This language looks like the set of all positive integers in base 10. “Looks like” is used instead of  “is” because L₃ is only a formal collection of strings of symbols. The integers have other mathematical properties If  L₃ is to be defined including the string ( word ) 0, then

    L₃ = { any finite string of alphabet letters that, if it starts with a 0 , has no more letters after the first }.  

  The box n is used as an end marker.  An illustration starts with a heading and terminates with and end marker. An old fashioned end marker denoting that a proof is finished is Q. E. D. The box serves the purpose.

Definition : The function “Length of a string” is the number of letters in the string. 

            If a = xxxx in the language L₁ then  length (a ) = 4  or directly  length ( xxxx ) = 4. 

            If c = 526 in the language L₃ , then  length (c )  = 3  or directly  length ( 526 )  = 3.

            In any language that includes the empty string  L ,  length ( L )  =  0

            For any word  w in any language,  if length ( w ) = 0  then  w =  L.

   Consider the language L₄ = { L  x   xx  xxx  xxxx  . . . } = { xⁿ   for  n =  0  1  2  3  . . . } 

            Here we say,  x ⁰  = L  and  not   x ⁰  = 1  as in algebra.  n

 Definition : Reverse function.  If  a is a word in some language L, then reverse ( a ) is the same string of letters spelled backward, called the reverse of a even if this backward string is not a word in L.

            Examples :       1.  reverse ( xxx ) = xxx                         2.  reverse ( 358 ) = 853         

                                    3.  In  L₃  reverse ( 650 ) = 056 which is not a word in L₃.  n

Definition :  Let us define a new language called PALINDROME over the alphabet ,  S = { a ,  b }.

            PALINDROME = { L ,  and all strings  x  such that reverse ( x ) = x }  n

            PALINDROME = { L,  a,   b,  aa,  bb,  aaa,  aba,  bab,  bbb,  aaaa,  abba . . . }

Definition :  Given an alphabet  S, we wish to define a language in which any string of letters from  S is a word, even the null string. This language, we shall call the closure of the alphabet. It is denoted by writing a star ( asterisk ) after the name of the alphabet as a superscript,  S*.   This notation is sometimes known as the Kleene star after the logician who was one of the founders of this subject.  

  Examples : 1.  If  S = { x } ,  then  S* = L₄ =  { L  x   xx   xxx  xxxx  . . . }  

                     2.  If  S = { 0 ,  1 }, then  S* = {  L   0   1   00   01   10    11    000    001 . . . }  

                     3. If  S = { a , b , c }, then  S*  = { L  a  b  c  aa   ab  ac  ba  bb  bc  ca  cb  cc  aaa . . . } n   

We can think of the Kleene star as an operation that makes an infinite language of strings of letters out of an alphabet. Infinite here means indefinitely many words each of finite length.

NOTE : When we wrote out the first several words in the language, we put them in size order ( words of shortest length first ) and then listed all the words of the same length alphabetically.

Kleene star

         In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*. It is widely used for regular expressions, which is the context in which it was introduced by Stephen Kleene to characterise certain automata.

        If V is a set of strings then V* is defined as the smallest superset of V that contains λ (the empty string) and is closed under the string concatenation operation. This set can also be described as the set of strings that can be made by concatenating zero or more strings from V.  

         If V is a set of symbols or characters then V* is the set of all strings over symbols in V, including the empty string.

Definition and notation :

           Given   V₀ = { l }  define recursively the set

                  V _{i + 1}  =  { wv : w  Π V_i  and  v  Î V }  where  i  ³ 0

If V is a formal language, then the i-th power of the set V is shorthand for the concatenation of set V with itself i times. That is, V_i can be understood to be the set of all strings of length i, formed from the symbols in V.

The definition of Kleene star on V is  V* =    È   V_i   =  { l } È V₁  È V₂  È V₃  È . . .                                                                                 

                                                                        ^{i ÎN}

That is, it is the collection of all possible finite-length strings generated from the symbols in V.

In some formal language studies, (e.g. AFL Theory) a variation on the Kleene star operation called the Kleene plus is used.   The Kleene plus omits the V₀ term in the above union. In other words, the Kleene plus on  V  is 

                     V ⁺  =   È   V_i   =  V₁  È V₂  È V₃  È . . .  

                                ^{i ÎN+}

 Example of Kleene star applied to set of strings:

{"ab", "c"}* = {λ, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}

Example of Kleene star applied to set of characters:

{'a', 'b', 'c'}*  =  {λ, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", ...}

Example of Kleene star applied to the empty set:

                                                                         Æ* =  { l } 

Example of Kleene plus applied to the empty set:

                                                                        Æ ⁺  =  Æ Æ*  =  { } =  Æ

Generalization    Strings form a monoid with concatenation as the binary operation and λ the identity element. The Kleene star is defined for any monoid, not just strings.

Definition : If  S  is a set of words, then by  S* is the set of all finite strings formed by concatenating words from S, where any word may be used as often as we like, and where the null string is also included.

   Example : If   S = { aa ,  b },  then  S*  = { L  plus any word composed of factors of  aa  and  b }

              = { L plus all strings  of  a’s  and  b’s  in which the  a’s  occur in even clumps }

              = { L  b  aa  bb aab  baa  bbb  aaaa  aabb  baab  bbaa  bbbb  aaaab  aabaa  aabb  baaaa

                     baabb  bbaab  bbbaa  bbbbb . . . }

The string  aabaaab is not in S* since it has a clump of a’s of length 3. The phrase clump of  “a’s”  has not been properly defined, but we know what it means anyway.

Example :   Let   S  =  { a , ab },  then

   S*  =  { L  plus any word composed of factors of  a  and  ab }

         = {L plus all strings of a’s and b’s except those that start with b and those that contain a double b} 

         = { L a  aa  ab  aaa  aab  aba  aaaa  aaab  aaba  abaa  abab  aaaaa  aaaab  aaaba  aabaa 

                        aabab  abaaa  abaab  ababa . . . }

 “Double b” means the substring bb. For each word in S* every b must have an a immediately to its left. The substring bb is impossible, as it is starting with a b. Any string without the substring bb that begins with an  a  can be factored into terms of  ( ab )  and  ( a ).   n

To prove that a certain word is in the closure language S*, we must show how it can be written as a concatenate of words from the base set S. In the above previous example, to show that abaab is in S*, we factor as follows :   abaab = ( ab ) ( a ) ( ab )    These factors are all in the set S; hence their concatenation is in S*. This is the only way to factor this string, hence the factoring is unique.

      Sometimes the factoring is not unique, i.e. 

            S = { xx ,  xxx }, then  S* = {  L  and all strings of more than one x }

               = { xⁿ   for  n  =  0,  2,  3,  4,  5,  . . . }

               = { L  xx   xxx   xxxx   xxxxx   xxxxxx . . . }

    Note that  x  is not in  S*.  The string  xxxxxxx is in this closure for any of this three reasons :

                        ( xx ) ( xx ) ( xxx )  or ( xx ) ( xxx ) ( xx ) or ( xxx ) ( xx ) ( xx ) .

Important to note here that the parenthesis  ( )  are not letters in the alphabet but are used for the sole purpose of demarcating the ends of the factors.

Proof by Constructive Algorithm – a method of proof based on showing that something exists ( i.e. by factoring) because we can describe how to create it.

 

      If the alphabet has no letters, then its closure is the language with the null string as its only word.

Symbolically, if  S = f ,  then  S* = { L }.  This is not the same as  if  S = { L }, then  S* = { L }.

  An alphabet may look like a set of one-letter words. If for some reason we wish to modify the concept of closure to refer only to the concatenation of some ( not zero ) strings from a set S, se use the notation  ⁺  instead of  *. 

Example :

            If  S = { x }, then  S ⁺ =  { x  xx   xxx    xxxx . . .  }  which is the language L₁ discussed before. 

If  S = { xx ,  xxx }, then  S ⁺  is the same as  S* except for the word L which is not in  S  ⁺ . This is not to say that  S ⁺  cannot in general contain the word L. It can, on condition that S contains the word  L. In this case L is in S  ⁺ , since it is the concatenation of some word from S ( L itself ). Anyone who does not think that the null string is confusing has missed something. It is already a problem, and it gets worse later.

             

If   S  is the set of three words,   S  =  { w₁  w₂  w₃ },  then 

                        S ⁺  = { w₁   w₂   w₃   w₁w₁   w₁w₂   w₁w₃   w₂w₁   w₂w₂   w₂w₃   w₃w₁   w₃w₂   w₃w₃

                                    w₁w₁w₁   w₁w₁w₂  . . . }.   No matter what the words w_1,  w_{2  and}  w₃  are. 

If  w₁ = aa,  w₂ = bbb and  w₃  = L ,  then  S ⁺  =  { aa   bbb   L  aaaa   aabbb . . . }.

 The words in the set  S are listed above in the order corresponding to their  w-sequencing ,  not in the usual size-alphabetical order.     

Applying the closure operator twice, yields the closure of  S* or  ( S* )* =  S**. The closure operator apply to infinite sets as well as to finite sets.

   THEOREM :  For any set  S  of strings we have  S*  =  S**.

            Example :  S = { a , b }, then  S*  is clearly all strings of two letters  a  and  b  of any finite length. Taking strings from  S*  and concatenate them and say we have concatenated  ( aaba ) , ( baaa ) and 

( aaba ). The result  ( aababaaaaaba )  is no more than a concatenation of the letters  a  and  b, just as with all elements of  S*.   ( aaba ) ( baaa ) ( aaba )

                            [ ( a ) ( a ) ( b ) ( a ) ] [ ( b ) ( a ) ( a ) ( a ) ] [ ( a ) ( a ) ( b ) ( a ) ]

                            ( a ) ( a ) ( b ) ( a ) ( b ) ( a ) ( a ) ( a ) ( a ) ( a ) ( b ) ( a )

Proof :  Every word in S** is made up of factors from S*. Every factor from  S*  is made up of factors from  S. Therefore, every word in  S** is made of factors from  S. Therefore, every word in  S**  is also a word in  S* which can be written in the form   S**  Ì  S*. 

            The symbol  “ Ì ” means “is contained in or equivalent to ”. In general, it is true that for any set A we know that A Ì A*,  since in A* we can chose as a word any one factor from A. So if we consider  A to be our set  S* then we have :  S*  Ì  S** .

                        Together, these two inclusions prove that   S*  =  S** .     

                                    Exercise  #s 2,  3,  4, 17   page  24 – 25.         

                                                     

 CHAPTER  3   *   RECURSIVE DEFINITION                  

                  – is characteristically a three-step process. 

1)      specify some basic objects in the set.

2)      Give rules for constructing more objects in the set from the ones we already know.

3)      Declare that no objects except those constructed in this way are allowed in the set.    

Recursive language

A recursive language in mathematics, logic and computer science, is a type of formal language which is also called recursive, decidable or Turing-decidable. The class of all recursive languages is often called R, although this name is also used for the class RP.

This type of language was not defined in the Chomsky hierarchy of (Chomsky 1959).

Definitions

There are two equivalent major definitions for the concept of a recursive language: A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language.

A recursive language is a formal language for which there exists a Turing machine which will, when presented with any input string, halt and accept if the string is in the language, and halt and reject otherwise. The Turing machine always halts; it is known as a decider and is said to decide the recursive language.

All recursive languages are also recursively enumerable. All regular, context-free and context-sensitive languages are recursive.

Closure properties

Recursive languages are closed under the following operations. That is, if L and P are two recursive languages, then the following languages are recursive as well: 

·   the Kleene star  L ^*

·   the concatenation  L o P

·   the union  L  È  P

·   the intersection  L Ç P

·   the complement of  L

·   the set difference  L − P

The last property follows from the fact that the set difference can be expressed in terms of intersection and complement.

If we try to define a set of even positive integers. One standard way of defining this set is :

EVEN is the set of all positive whole numbers divisible by 2; or EVEN is the set of all 2n,

 where  n = 1 2  3  4 . . .  A third method is by recursive definition. EVEN is defined by these three rules:

      Rule  1 :  2 is in EVEN.

      Rule  2 :  If  x is EVEN  then so  is  x + 2.

      Rule  3 :  The only elements in the EVEN are those that can be produced from the two rules above.

  Ex. 1.  Prove that 10  is in the EVEN set.

      By defn 1) divide 10 by 2, there is no remainder; hence 10 is in EVEN set

      By defn 2) 10 = ( 5 )( 2 ) ; hence 10 is in EVEN.

      By defn 3) recursive definition :  by rule 1, we know  2 is in EVEN; then by rule 2  we know that

                   2 + 2  = 4  is in EVEN.  Since 4 is in EVEN then by rule  2 ,   4 + 2 = 6 is in EVEN. By rule 2,

                   6 + 2  = 8  is in EVEN. By rule 2 ,  8 + 2 = 10 is in EVEN set; hence 10  is in EVEN. 

Alternately; the set EVEN is defined by these rules :

       Rule 1 :  2  is  in EVEN.

       Rule 2 :  If  x  and  y  are both in EVEN then so is   x  +  y.

       Rule 3 :  No number is in EVEN unless it can be produced by Rules  1  and  2.

 To solve the above example :

     By rule  1 :  2  is  in  EVEN

     By rule  2 :  x = 2 ,  y = 2  ®  4  is in EVEN

     By rule  2 :  x = 2 ,  y = 4  ®  6 is in EVEN

     By rule  2 :  x = 4 ,  y = 6  ® 10  is in EVEN.

             A polynomial is a finite sum of terms each of which is of the form a real number times a power of x  ( that may be  x⁰ = 1 ).

     The set POLYNOMIAL  is defined by these four rules :

            Rule 1 :  Any number is in POLYNOMIAL.

            Rule 2 :  The variable x is in POLYNOMIAL.

            Rule 3 :  If  p  and  q  are in POLYNOMIAL, then so are  p + q  and ( p ) and  pq.

            Rule 4 :  POLYNOMIAL contains only those things which can be created by the 3 rules above.

   Ex. 2.  Show that  5x²  +  4x – 8  is in POLYNOMIAL.

     By rule  1 :  5  is in POLYNOMIAL          

     By rule  2 :  x  is in POLYNOMIAL

     By rule  3 :  ( 5 )( x ) is in POLYNOMIAL, call it  5x

     By rule  3 :  ( 5x )( x ) is in POLYNOMIAL,  call it  5x²   

     By rule  1 :  4  is in POLYNOMIAL

     By rule  3 :  ( 4 )( x )  is in POLYNOMIAL

     By rule  3 :  5x²  +  4x  is in POLYNOMIAL. 

     By rule  1 :   –8  is  in POLYNOMIAL

     By rule  3 :  5x²  +  4x  + (–8 ) = 5x²  +  4x  – 8  is in POLYNOMIAL.

  Ex.  3.  Show that  24  is in EVEN set

  Ex.  4.  Show that  2x² – 3x  +  2  is in POLYNOMIAL.  

  Ex.  5.  Show that  7x²  +  3x  –  11  is in POLYNOMIAL.

  Ex.  6.  Show that   x² – 12x  +  18  is in POLYNOMIAL.

Arithmetic Expressions ( AE )

            Supposed we ask ourselves what constitutes a valid arithmetic expressions that can be typed on one line, in a form digestible by computers. The alphabet of this language is :

            S = { 0  1  2  3  4  5  6  7  8  9   +  -  *  /  (   )  }

  It is obvious that the following strings are not good :

            ( 3 + 5 )  + 6 )              2( /8  +  9 )                   ( 3 + ( 4 - ) 8 )              2 ) – ( 4

   ( 3 + 5 )  + 6 ) – contains an unbalanced parenthesis.                      

   2( / 8  +  9 ) – contains a forbidden substring  ( /

   ( 3 + ( 4  – ) 8 )  – contains the forbidden substring  – )                   

   2 )  –  ( 4   –  contains  a close parenthesis before the corresponding open parenthesis.

//  and  */  are also forbidden in arithmetic expressions.

            The most natural way of defining a valid arithmetic expression is by using recursive definition.

The definition can be written as :

            Rule 1 :  Any number of ( positive, negative, or zero ) is in AE.

            Rule 2 :  If x is in AE, then so are ( x )  and  – ( x ).

            Rule 3 :  If  x  and  y  are in AE, then so are

                        ( i )  x + y  ( if the first symbol in y is not  – )

                        ( ii )  x – y  ( if the first symbol in y is not  – )

                        ( iii )  x * y

                        ( iv )  x / y

                        ( v )  x ** y   ( our notation for exponentiation )

   This is the most natural definition because even if we have not articulated at this point, it truly is the method for recognizing arithmetic expression in real life. Given the expression with

                                                ( 2 + 4 ) * ( 7 * ( 12 –  4 ) / 4 * 2 ( 2 + 8 ) – 1   

      and asked to determine if it is a valid expression, we do not really scan over the string looking for forbidden     

      substrings or count the parentheses. This can broken down into components and verify whether it is ok or not. 

     Clear expressions :     2 + 3 + 4 ,     12 – 3 + 4

     Ambiguous expressions :   8/4/2  which may be equal to  4  or  1

                                                3 + 4 * 5  which may be equal to  23 or 35

    Hence, we adopt conventions for operator hierarchy and left to right execution.  By applying Rule 2, we can place enough parenthesis to avoid any confusion. This definition adequately defines the language of all valid strings of symbols for arithmetic expressions.  Remember that the ambiguity in the string  8/4/2 is a problem of meaning.  There is no doubt that the string is a word in AE, only doubt about what it means. This definition determines the set AE in a manner useful for proving many theorems about arithmetic expressions.

   Theorem 2 : An arithmetic expression cannot contain the character $.

     Proof by constructive algorithm:

            $ is not part of any number, so it cannot be introduced into an AE by Rule 1. If the character string x does not contain the character $, then neither do the strings ( x ) and – ( x ), so it cannot be introduced into an AE by Rule 2. If neither  x  nor  y contains the character  $, then neither do any of the expressions defined by Rule 3. Therefore, the character $ can never get into an AE.

   Theorem 3 :  No  AE can begin or end with the symbol /.

    

     Proof by constructive algorithm:

               No number begins or ends with this symbol, so it cannot occur by Rule 1. Any AE formed by Rule 2 must begin and end with parentheses or begin with a minus sign, so the / cannot be introduced by Rule 2. If x does not begin with a / and y does not end with a /, then any AE formed by any clause in Rule 3 will not begin or end with a /. Therefore, these rules will never produce an expression beginning or ending with a /.     ( The symbol / in computer science is “slash”, other names are “oblique stroke”,

                                     “solidus” or “virgule”).

 Theorem 4 :  No AE can contain the substring //.

 Proof :  For variation, we shall prove this by contradiction, even though a direct argument similar to those above could easily be given.

           Let us suppose that there were some AE’s that contained the substring //, but there is no shorter word in AE that contains this substring. There may be more strings of the same length as w that contains //, but it does not matter which of these we begin with and choose to call w.

           We know that w like all words in AE, is formed by some sequence of applications of the Rules 1, 2 and 3. The first question is:   Which was the last rule used in the production of w ?  It must have been Rule 3(iv). If it were Rule 3(iii), for instance, then the double slash must either be found in the x part or the y part. But x and y are presumed to be in AE so this would mean that there is some shorter word in AE than w that contains the substring //, which contradicts the assumption that w is the shortest, similarly, we can eliminate all the other possibilities. Therefore the last rule used to produce  w  must have been 3 (iv).

           Now, since the // can have been contributed to w from the  x  part alone or from the  y  part alone ( or else x or y)  are shorter words in AE with a double slash , it must have been included by finding an x part that ended in / or a y part that begin with a /. But since both x and y are AE’s, our previous theorem says that neither case can happen. Therefore even Rule 3(iv) cannot introduce the substring //.

     Therefore, there is no possibility left for the last rule from which w can be constructed. Therefore, w cannot be in the set AE. Therefore there is no shortest AE that contains the substring //. Therefore, nothing in the set AE can have the substring //.  n  

     This method of argument should familiar. It is similar to the proof that { xx, xxx }* contains al  xⁿ , for n ¹ 1. 

 Another common use of the recursive definitions is to determine what expressions are valid in Symbolic Logic. We shall be interested in one particular branch of Symbolic Logic called Sentential Calculus or the Propositional Calculus. The version we shall use here uses only negation  Ø  and implication ®  along with the phrase variables, although conjunction and disjunction could easily be added to the system. The valid expressions in this language are traditionally called WFF’s for Well-Formed Formulas. As with AE, parentheses are letters in the alphabet.

                                    S = { Ø  ®  ( )  a b c d . . . }

         There are other symbols sometimes used for negation, such as ⌐ , – , and the rules for forming WFF’s are :

            Rule  1:   Any single Latin letter is a WFF. 

                                             a  b  c  d . . .

            Rule  2 :  If p is a WFF, then so are  ( p )  and  Ø p .

            Rule  3 :  If p and q  are  WFF’s, then so is   p ® q .

   Some sequences of applications of these rules enables us to show that :

                        p ® q (( p ® q ) ® q )  is a  WFF. Without  too much difficulty we can also show that :

                        p ®   ® q   ( p ®      p )      p)  ®  p (  are not all  WFF’s.

Physics E 101 Lesson 1

                                 Physics : INTRODUCTION 

Physics is a major science, dealing with the systematic study of the basic properties of the universe, the forces they exert on one another, and the results produced by these forces. Physics is closely related to the other natural sciences and, in a sense, encompasses them. Chemistry, for example deals with the interaction of atoms to form molecules. Much of modern geology is largely a study of the physics of the earth and is known as geophysics. Astronomy deals with the physics of the stars and outer space. Even living systems are made up of fundamental particles and, as studied in biophysics and biochemistry, they follow the same type of laws as the simpler particles traditionally studied by a physicist.
The emphasis on the interaction between particles in modern physics, known as the microscopic approach, must often be supplemented by a macroscopic approach that deals with larger elements or systems of particles. This macroscopic approach is indispensable to the application of physics to much of modern technology. Thermodynamics, a branch of physics developed in the 19th century, deals with the elucidation and measurement of properties of a system as a whole and remains useful in other fields of physics; it also forms the basis of much of chemical and mechanical engineering. Such properties as the temperature, pressure and volume of a gas have no meaning for an individual atom or molecule; these thermodynamic concepts can only be applied directly to a very large system of such particles. A bridge exists, however, between the microscopic and macroscopic approach; another branch of physics; known as statistical mechanics, indicates how pressure and temperature can be related to the motion of atoms and molecules on a statistical basis.
Physics emerged as a separate science only in the early 19th century, until that time a physicist was often also a mathematician, philosopher, chemist, biologist, engineer, or even primarily a political leader or an artist. Today, the field has grown to such an extent that with few exceptions modern physicists have to limit their attention to one or two branches of the science. Once the fundamental aspects of a new field are discovered and understood, they become the domain of engineers and other applied scientist. The 19th century discoveries in electricity and magnetism, for example, are now the concentrations of electrical and communication engineers; the properties of matter discovered at the beginning of the 20th century have been applied in electronics; and the discoveries of nuclear physics, have passed into the hands of nuclear engineers for applications to peaceful or military uses.

MATHEMATICS as a language of science
Mathematics is the language of physics; that is when ideas in science are expressed in mathematical terms:
1. They are unambiguous.
2. They do not have double meanings, that so often confuse the discussion of ideas expressed in
common language.
3. They are easier to verify or disprove by experiment.
4. The methods of mathematics and experimentation led to enormous success in science.
5. The abstract mathematics developed by mathematicians is often years later found to be the
exact language by which nature can be described.
Mathematics is the language of physics does not mean that mathematics is physics or physics is mathematics.

THE SCIENTIFIC METHOD – is a method that is extremely effective in gaining, organizing, and applying new knowledge. The steps are :
1. Recognize a problem.
2. Make an educated guess --- a hypothesis. Hypothesis is an educate guess that is only considered factual after it has been demonstrated by experiments. If a hypothesis has been tested over and over again and has not been contradicted it may become known as a law or principle.
3. Predict the consequences of the hypothesis
4. Perform experiments to test predictions.
5. Formulate the simplest general rule that organizes the three main ingredients --- hypothesis, prediction, and experimental outcome --- into a theory.
The success of science has more to do with an attitude common to scientists than with a particular method. This attitude is one of inquiry, observation, experimentation and humility.

THE DOMAIN OF PHYSICS

A. According to size of objects studied
1. Quantum domain – the domain of small objects. Objects are considered small if their sizes are
comparable to or smaller than the size of an atom.
2. Non-quantum domain – the domain of large objects. Objects are considered large if they are larger than the size of an atom.

B. According to speed of objects studied
1. Relativistic domain – the domain at high speed, that is if the speed of the moving object is comparable to
the speed of light.
2. Non-relativistic domain – the domain at low speed, that is the speed of the moving object is less than the
speed of light.

C. Newtonian domain – a combination of the division according to size and speed. It is the domain of large
objects at low speeds, the one we deal in our daily lives. (In honor of Sir Isaac Newton, the 17th century
physicist who played the key role in developing the physics of large objects moving at low speed).

D. Mechanics – is the study of the relation between the force and the resulting motion. It seeks to account
quantitatively for the motion of objects having given properties in terms of the force acting on them.

1. Newtonian mechanics – is the mechanics of the Newtonian domain. It deals with systems containing
objects which are large and which move at low speed.

2. Relativistic mechanics – is the mechanics of the relativistic domain. In 1905, Einstein showed that a
different approach was necessary for the study of objects moving at speeds so high as to be comparable
to the speed of light.

3. Quantum mechanics – is the mechanics of the quantum domain. It was developed about the same time
with relativistic mechanics by Max Planck, Louis de Broglie, Erwin Schrodinger and others. They found
out that the Newtonian mechanics could not explain the motion of objects whose size is in the atomic
scale or smaller.

E. Electromagnetism – is the study of the properties and consequences of the electromagnetic force, which is
one of the fundamental forces in nature. The fundamental forces are gravitational force, electromagnetic
force, strong nuclear force and weak nuclear force.

F. Solid-state physics is a branch of physics that deals with the properties of solids. A particular problem in
solid – state physics, for instance the properties of materials use in transistors, is solve by employing the
mechanics of whichever domain is most appropriate.

G. Heat and Thermodynamics


THE FUNDAMENTAL MEASURABLE QUANTITIES IN PHYSICS
1. Length 3. Time 5. Luminous intensity 7. Molecular quantity
2. Mass 4. Temperature 6. Electric charge ( current )

THE FUNDAMENTAL MEASURABLE QUNATITIES IN MECHANICS
1. Length 2. Mass 3. Time



Measurement is a scientific comparison between an unknown quantity to a fixed known quantity called standard.

Systems of Measurement
1. English system (British Engineering system) – originated in England
2. Metric system – originated in France

Systeme International d’Unites ( SI ) adopted by the International Bureau of Weights and Measures in 1960.
The units of the MKS is adopted as the base units of the SI system.


Base Units of each System of measurement

Measurable Quantities in Mechanics Metric System English System
CGS MKS FPS
Length Centimeter ( cm ) Meter ( m ) Foot ( ft )
Mass Gram ( g ) Kilogram (kg ) Slug ( lbm )
Time Second ( s ) Second ( s ) Second ( s )

Reasons for adopting the Metric system:
1. It is scientifically planned.
2. It is a decimal system.
3. It is universally accepted.

DISADVANTAGES OF THE ENGLISH SYSTEM
1 yard = ( King Henry I ) distance from the tip of his nose to the end of his thumb
1 inch ( 1324 ) = length of three grains of barleycorns laid end to end
1 mile = 1000 double step of an average soldier
1 foot = length of the foot of the king

THE CONCEPT OF THE METER
To be discuss in class with demonstrations

Technical Writing

Tips on report writing

Visit the site by clicking this statement

Click : Tips on Writing a Thesis Essay  

CITE CHEER DANCE 2011

Momentum, Fluids and PHYSICS 201 Assignment

     PHYSICS 201 ASSIGNMENT ----- to be submitted on or before 
                                                     2:00 PM October 12, 2011  


1. A consumer electric meter reads 211245 on July 30, 2010 and on August 30, 2010 it reads 211357. The reading indicates the total energy consumed by the consumer for the month in kilowatt hours. If energy rate is P 5.75 per kilowatt hour, determine the total electric bill of the consumer for the month.

2. A ball with a mass of 500 grams is thrown with a velocity of 12 m/s. Determine the impulse imparted to the ball. If the throwing was done in 0.3 second, what is the force imparted to the ball ?

3. An 10 g bullet was fired to a 790 g block of wood suspended on a long cord. If the bullet is embedded in the block, and the center of mass of the block-bullet is raise to a height of 12 cm, determine the initial speed of the bullet.

4. Mercury has a specific gravity of 13.6. What is the mass of 800 cm3 of mercury? What is the volume in cubic meter of 2000 g of mercury ?

5. A swimmer dives into a lake, and was submerge to a height of 8 m from the surface. What is the pressure experience by the swimmer at this depth of the water ?

6. A 500 g ball is drop from a height of 40 m. What is the momentum of the ball upon reaching the level ground? What is the maximum potential energy of the ball?

7. What is the impulse of the ball in problem # 6, 1.75 seconds after it was released ? What is the potential and kinetic energy of the ball at this level above the ground?

8. The volume of an irregular nugget of iron is to be determined but no weighing scale is available. The iron is place into a cylinder with water. If the diameter of the cylinder is 12 cm, and the water level rises to a height of 15 cm, what is the volume of the nugget in cubic meter ?

                                                  E N D

CONSERVATION OF MOMENTUM

 1. Momentum is the product of mass and velocity. It is a vector quantity and its direction is towards the direction of the velocity.

 2. Impulse is the product of force and time during which the force acts. The impulse is equal to the change in

            momentum.

 3. Elastic bodies are bodies which return to their original shapes after a temporary deformation during collision.

 4. Law of Conservation of momentum. If tow or more bodies interact, the momentum after the interactions is equal to the momentum before interaction.  The total momentum of any system of bodies is unchanged by any interactions between the different members of the system.

 5. Resilience is the ability of a body to undergo compression or rapid deformation without the development of permanent deformation.

 6. Restitution is the vigor (energy) with which a body restores to its original shape and size after deformation.

 7. Coefficient of restitution ( r ) the ratio of the velocity with which the two bodies separate after collision to the velocity of approach before collision.

                        r = 1  for perfectly elastic collision

                        r = 0  for perfectly inelastic collision

                        r = between  0  –  1  for semi-elastic collision.   

COLLISION PHENOMENA

  1.  In a perfectly elastic collision, kinetic energy as well as momentum is conserved. The velocity of approach is equal to the velocity of separation in magnitude but opposite in direction. ( NOTE : No perfectly elastic collision for macroscopic bodies ).    Ex.  Collision between atomic nuclei, atoms, molecules and electrons

  2.  Inelastic collision is any collision for which the final kinetic energy is less than the initial kinetic energy.

  3.  Perfectly inelastic collision is any collision wherein the two colliding bodies sticks together indefinitely. The colliding bodies are permanently deformed and never separate, hence both have the same final velocity and the velocity of separation is zero since the two bodies sticks together.

  4.  Semi-elastic collision is a type of collision that is not perfectly elastic.

   NOTE :

          1. In every collision momentum is conserved, kinetic energy is conserved only in perfectly elastic collision. 

LIQUIDS  AT  REST

 Fluid is a term applied to liquids and gases, for they flow readily and do not resist shearing stress.

      a) Liquid occupies a well-defined volume having no shape of its own, but takes the shape of the

                  vessel containing it. A liquid readily changes shape in response to forces. It offers large

                   resistance to efforts to change its volume. Most liquids are incompressible.

     b) Gas completely occupies any enclosed volume in which it is placed. Gases are readily

                   compressible and it is relatively easy to reduce the volume of a gas to any desired size.

 Density is the ratio of the mass of a substance to its volume.

 Weight density is the ratio of the weight of an object to its volume.

 Specific gravity is the ratio of the density of any substance to the density of water.  

Pressure is the ratio of the force to the area where it is applied. The unit of pressure is Pascal, 1 Pascal = 1 N/ m²

 In meteorology, the unit of pressure is millibar  and  1 bar = 1.0  x  10⁵ N/ m²  

FLUIDS AND PRESSURE

       Fluid is any substance that cannot maintain its own shape or has no rigidity. Fluid is a term applied to liquids and gases for they flow readily and they do not resist shearing stress. Fluids can flow and alter its shape to conform to the outlines of its container. Both liquids and gases have many characteristics in common. Liquids are nearly incompressible, while gases are easily compressed. Liquids tend to have greater density than gases. The gaseous phase of a substance usually exists at higher temperature, hence gas molecules are able to break free from one another.  Gases are able to escape from an open container, whereas liquids cannot.

PRESSURE

       Pressure is the force applied per unit area, P = F/A where F is the force applied and A is the area on which it is applied. Pressure is one of the important concepts in fluids. Examples of pressure: record player needle exerts pressure  on a disc record, water near the bottom of a pool exerts pressure on a swimmer’s eardrum, and atmospheric pressure changes weather conditions. Measurements of pressure are common : Tires must be inflated to correct pressure, blood pressure should stay within normal range, and too much pressure in the eye ( glaucoma ) can cause blindness.

      The SI unit for pressure is Pascal ( Pa ); 1 Pa = 1 newton / m². An atmosphere ( atm ) is also a unit of pressure, where one atm = the average pressure due to the weight  of the atmosphere at sea level.

       Pressure is as important as the force creating it. If someone pokes you with his finger, you will certainly feel it. If, however, a nurse pokes you with a hypodermic needle using the same amount of force, you just don’t feel it – the needle breaks the skin. The same force applied to a smaller area creates a larger pressure and has a much different effect.

       Fluids as well as solids, can exert pressures. Consider the water in a square container. If the water has a mass of 10 kg, its weight of 98 N must be supported by the bottom of the container. If the bottom has  an area of 0.1 m², then the pressure due to  the weight of the water on the bottom is 980 N / m². This computation is valid only for containers with straight sides. Another example is atmospheric pressure, which is caused by the weight of air. Atmospheric pressure is 1.013 x 10⁵ Pa at sea level which means a column of air 1m on a side extending to the top of the atmosphere weighs 1.013 x 10⁵ N. Stationary fluids always exert forces perpendicular to surfaces whether that direction is up or down, left or right. The reason the force is always perpendicular to the surface is that fluids cannot withstand shearing or sideways forces and therefore cannot exert sideways forces.

   1. A woman wearing high-heeled shoes places about 50 % of its full weight on the single heel when walking. If the woman has a mass of 50 kg, determine the pressure on the ground under one heel if the area of contact is

       2.5 cm². How would this pressure compare with the pressure exerted underneath the elephant’s foot which is circular with diameter of 30 cm assuming that it is standing on four legs and with mass of 3 776 kg.  

      2. Determine the pressure in N / m² and atm exerted by a phonograph needle on a record surface if the needle

       supports 2.4 g on a circular area 0.48 mm in diameter. 

   3. Calculate the force exerted on one side of a 3 m by 9 m wall assuming normal atmospheric conditions.

CONVERSION FACTORS FOR VARIOUS UNITS OF PRESSURE

Conversion to N / m2			Conversion to  atmosphere ( atm )
1.0  atm	=	1.013 x 105 N/m2	1.0  atm	=	1.013 x 105 N/m2
1.0 dyne/cm2	=	0.1 N/m2	1.0  atm	=	1.013 X 106dyne/cm2
1.0 kg/cm2	=	9.8 x 104 N/m2	1.0  atm	=	1.03 kg /cm2
1.0 lb/in2	=	6.9 x 103 N/m2	1.0  atm	=	14.7 lb/in2
1.0 mm Hg	=	133 N/m2	1.0  atm	=	760 mm Hg
1.0 cm Hg	=	1.33 x 103 N/m2	1.0  atm	=	76 cm Hg
1.0 cm water	=	98.1 N/m2	1.0  atm	=	1.03 x 103cm water
1.0 bar	=	1.0 x 105 N/m2	1.0  atm	=	1.013 bar

PASCAL’S PRINCIPLE
One pioneer in the Physics of fluids was the French philosopher and scientist Blaise Pascal ( 1623 – 1662 ). He discovered an important property of stationary fluids: They can be used to transmit pressure to a place other than where the pressure is created and is not diminished while in transit. This is Pascal’s principle : Any pressure applied to a confined fluid will be transmitted undiminished to all parts of the fluid.


Gauge pressure is the pressure above or below atmospheric pressure. Total pressure or absolute pressure is gauge pressure plus atmospheric pressure.
Pt = Pg + Patm, where Pt = total pressure, Pg = gauge pressure, Patm = atmospheric pressure


Pascal’s principle is applicable to hydraulic systems. It is important to note that pressure, not force is transmitted undiminished to all parts of the fluid.

P₁ = P₂  ==>  F₁ / A₁ = F_{2 / A2}

_{Pascal’s principle holds for gases as well as for liquids, with some minor modifications due to the change in volume of a gas when the pressure is changed.}

_{Hyperbaric medicine treats many physical problems through the application of high-pressure air or air-oxygen mixtures. Patients are enclosed in chambers pressurized up to 6 atmospheres. By Pascal’s principle, the pressure is distributed throughout the hyperbaric chamber. Patients breathing air at 6 atmospheres takes in six times the amount of oxygen with each breath. The increased oxygen intake is useful in treating a variety of problems such as carbon monoxide poisoning, slow-healing of wounds, and burns.}

_{1. The large piston of a hydraulic press supports a dentist’s chair and the dentist wants to lift the patient by}

_{stepping on the pedal directly on top of the small piston. Find the force exerted by the dentist if the patient plus}

_{chair have a mass of 125 kg and the large piston has radius of 6 cm and the small piston has radius of 1.2 cm.}

_{PRESSURE DUE TO WEIGHT OF A COLUMN OF FLUID}

_{P = F / A = mg /A , but m = pV   =>  P = pVg / A   =>  V = Ah   =>  P = pAhg /A  =>  P = hpg}

_{The pressure due to the weight of a column of fluid depends only of the depth in the fluid and the density of the fluid. Pressure at the surface of a fluid is zero since h is zero. As it goes deeper the pressure increases in proportion to the increase in height.}

_{Another manifestation of how pressure depends only on depth and density, is found in the intravenous ( IV ) administration of fluids. The pressure due to the IV fluid at the entrance of the needle is proportional to h, the height of the surface above the needle. Paths of the fluid has nothing to do with pressure but is dependent on h,  P = hpg. Applied pressure can be adjusted by raising or lowering the IV bottle relative to the patient.}

_{Problems :}

_{1. A nurse administers medication in a saline solution to a patient by infusion into a vein in the patient’s arm. The}

_{density of the solution is 1000 kg/m³, and the gauge pressure inside the vein is 2.7 x 10³ Pa. How high above the}

_{insertion point must the container be hung so that there is sufficient pressure to force the fluid into the patient ?}

_{2. A scuba diver searches for treasure at a depth of 22 meters below the surface of the sea. At what pressure}

_{must the scuba device deliver air to the diver? How many atmospheres would this pressure be ?}

_{Note : The pressure at the diver’s depth is greater than atmospheric pressure because of the weight of the}

_{water above the diver. If the air breathed in is not at the same pressure as the external pressure on the}

_{diver’s chest, the excess pressure will collapse the chest. Thus, the breathing apparatus must deliver}

_{air to the diver at the pressure of the surrounding water. ( use P = Patm + hpg )}

_{3. A tank is filled with water to a depth of 175 cm. What is the pressure at the bottom of the tank due to the}

_{water alone ? What is the total pressure ?}

_{MEASUREMENT OF PRESSURE BASED ON PASCAL’S PRINCIPLE AND  P = hpg.}

_{Pascal’s principle states that any pressure applied to a confined fluid is transmitted undiminished to all parts of the fluid. Thus, fluid can be use to transmit pressure to a gauge at a convenient location. As an example, blood pressure can be measured without putting a gauge into the body. Furthermore, pressure is transmitted undiminished, so the measurement can be very accurate. In a blood pressure measurement, an inflatable cuff is placed on the upper arm, and inflated until blood flow is cut off in the brachial artery. Pressure is created by squeezing the bulb and is transmitted by air in the tubes (a confined fluid) to the cuff and to the gauge. The wall of the cuff transmits the pressure to the arm and through it to the artery . When the applied pressure exceeds the heart’s output pressure , the artery collapses. The person making the measurement slowly releases the air in the cuff, lowering its pressure, and listens for flow to resume when pressure in the cuff becomes lower than the maximum heart output.}

_{Systolic blood pressure, ( when the heart is contracted ) the maximum blood pressure is recorded together with the lower pressure called the diastolic pressure (when the heart is relaxed between beats). Diastolic pressure is the minimum pressure the circulatory system experiences and can be detected as a change in the sound of the blood flow through the partially restricted artery. The main point here, based on Pascal’s principle, is that all these pressures are transmitted undiminished and the pressure read by the gauge is truly representative of the pressure in the heart. It is important for the cuff to be at the same level as the heart in a blood pressure measurement. Any effect due to the weight of the air in the cuff and connecting tubes is negligible because the density of air is very small. The gauge can be placed at any convenient location, such as on the wall, a table, the floor, or anywhere in between, but the cuff must be at the same level as the heart.}

_{4. Determine the maximum force in newtons exerted by the blood on an aneurysm, or ballooning, by}

_{the aorta, given that the maximum blood pressure is 140 mm Hg and the area of the aneurysm is 25 cm².}

_{F = PA = ( hpg ) A = ( 0.140 m )( 13 600 kg/ m³ ) ( 9.8 m /s² )( 25 cm² x 1 m²/ 10 000 cm² ) = 46.648 N}

_{Note that the fluid involve is mercury, hence we use 13 600 kg/ m³ for the density of mercury and convert 140 mm to meter. The area 25 cm² is likewise converted to m² .}

 _{>>> This is a large force for the vessel to withstand, and there is a considerable risk that the aneurysm will burst.}

_{5. [ 6.10 / 176 ] Water towers are used to store water above the level of homes. If a user observes that}

_{the static water pressure at home is 3 x 105 N /m2, how high above the home is the surface of the}

_{water in the tower ?}

_{BUOYANT FORCE AND ARCHIMEDES’ PRINCIPLE}

_{A story has been told that Archimedes ( 287 – 212 B. C. ) conceived of the principle that bears his name after King Hiero of Syracuse asked him to determine the actual composition of the King’s crown, which was alleged to be pure gold. Archimedes was ordered to do so without damaging the crown.}

_{According to legend, the Greek scientist’s inspiration came to him as he lay partially submerged in his bath. On getting into the tub, he observed that the more his body sank into the tub, the more water ran out over the top. He immediately jumped out of the tub and rushed through the streets naked, shouting excitedly in a loud voice “Eureka” (“I have found it”). Archimedes’ principle states that : A body whether completely or partially}

_{submerged in a fluid, is buoyed upward by a force that is equal to the weight of the displaced fluid.}

_{Buoyant Force = weight of displaced fluid  ==> FB = wd.l.}

_{The principle applies both to liquids and gases and to objects which are completely or partially submerged. How this principle allowed Archimedes to solve the problem of the king’s crown is shown in the following problem:}

_{The King’s crown is said to be solid gold but maybe made of lead and covered with gold. When it is weighted}

_{in air, the scale reads 0.475 kg. When it is submerged in water, the scale reads 0.437 kg. Is it solid gold ? If not, what percentage by mass is gold?} 

_{BOYLE’S LAW}

_{Robert Boyle ( 1627 – 1691 ) advanced the study of gases using an air pump made by Robert Hooke. Boyle observed the relationship between the pressure and the volume of an enclosed gas at constant temperature. Boyle’s law states that at constant temperature the pressure exerted by a gas is inversely proportional to the volume in which it is enclosed.}

_{P a1/ V  =>  PV = k or PV = constant, where P is the gas pressure, V is the volume and the value of the constant depends on the initial conditions. A complete statement of Boyle’s law includes the}

_{condition that both the temperature and the amount of gas must be held constant. Alternatively, Boyle’s}

_{law can be written in the form P1V1 = P2V2 ; where the subscripts 1 and 2 refer to the different physical states of the same sample of gas with the temperature held constant.} 

_{1. A cylinder with height of 20 cm and cross sectional area of 0.40 m² has a close-fitting piston that may be moved to change the internal volume of the cylinder. Air at 1.013 x 10⁵ N/m² fills the cylinder. If the piston is pushed until it is within 8 cm from the end of the cylinder, what is the new pressure of the air? Assume that the temperature of the gas remains constant and that the volume of gas in the gauge is small compared with the volume of the cylinder.}

MATH E 111 / MATH 101 ASSIGNMENT

 
 Assignment to be submitted on October  3,  2011  10:00 AM

 

1.       Of the 800 tickets sold to a movie, 480 were adult tickets. The total gate receipts is  Php  2080. How much is the cost of students ticket  if an adult ticket cost  Php 3 ?

2.       An empty swimming pool can be filled in 10 hours by an inlet faucet and when full it can be drained empty by an outlet faucet in 19 hours.  How long will it be filled if the outlet faucet  is accidentally left open when filling starts ?

3.       A nurse has  1  liter of solution that is 20 % alcohol. How much pure alcohol must she add to bring it to a solution that contains 30%  alcohol ?

4.       John scored 5 points higher on his midterm, and 13 points higher on his final, than on his trinal exam. What did he score  on the trinal exam if his average score was 90 ?

5.       The sum of three consecutive positive odd  integers  is  69. Find the integers.

6.       A child has equal number of nickels, dimes and quarters. If the coins are worth  $ 3.20, how many of each types of coin are there?

7.       A motorboat  travels  5 km upstream in the same time that it requires to go 7 km downstream.  If the river’s current flows at the rate of  2 km/hr , what is the speed of the motorboat  in still water ?

8.       One morning John drive to his uncle’s house in a distant city in 5 hours. When he returned home, there was less traffic and the trip took only 3 hours. If John drive  26 km per hour faster on the return  trip, how fast did  he drive in each way ?

9.       If Roy is 12 years old and his father  40 years old, in how many years will Roy’s age  become one-half his father’s age.

10.   Determine the present age of a man if  ½  of his age 8 years ago is equal to  ¼  of his age 12 years from now.

11.   If a certain number is added to both the numerator and denominator of the fraction 3/5 , the resulting fraction is  5/6.  Determine the number.

12.   A man invest some money at  8 %  interest and twice as much at  9 %  annual  interest.  The total income from his two investments  is  Php 2,080.  How much did he invested at each rate ?

13.   It is now  4:00 o’clock PM.  At what time before 5:00 o’clock will the minute hand and the hour hand  become  (a) perpendicular for the first time,  (b) perpendicular for the second time.  (c)  What time will the minute hand overtake  the hour hand ?

14.   If   Php  500.00  is invested  at 16 %   simple  interest,  how  many  years  will  it  take to have a final

        amount of P 900.00 ?

15.   An ant travels  140 cm to the north, then turns  60 cm  to the east and then  60 cm  to the south. How far is the  ant from the starting point ?

                             E N D       E N D         E N D

                              



 

I. Solve for the value of x

1.    3( x + 5 )  =  3( 1 + x )

2.    3( x + 2 )  =  5x + 2

3.         2         =   1
        3 - x

4.     2 + x    +      x + 7     =    4x  +  1
          3                   2

5.    x² - 8x + 15  =  ( x – 3 )( x + 5 )

6.         3         =    1
         x - 3

7.     x ( x + 2 ) = ( x + 1 )²

8.     3x + 1     =    ½
           20

9.        1          =    3
         x + 1

10.   3 ( x + 2 )  –  x   =  2 ( x + 3 )

II. Use algebraic translation to find the required unknown.

1. Find three consecutive odd numbers whose sum is 105.

2. Find two consecutive positive even numbers whose squares differ by 60.

3. The length of a rectangular garden is 5 m longer than its width. If the perimeter is
    78 , determine the length and the width of the garden.

4.   Two angles are supplementary. Determine their magnitudes if one angle is 48 degrees greater than the
   other.

5.  A   BSCS  student makes a grade of  72 %, 68 % and 78% in his three subjects. What should be his
         grade in the fourth subject so that he will have an average grade of  80% ?