COSC3302                            Final Exam Review.              Spring 2013                           

 

 

  NAME__________________________________________________

 

  THROUGHOUT THIS TEST, THE FOLLOWING NOTATIONS ARE APPLICABLE:

 

                1.             RE:                          Recursively Enumerable

                2.             PC:                          Partially Computable

                3.             FSA:                       Finite State Acceptors (Deterministic or otherwise)

4.             S.L.                         The Simple Language with the following three basic instructions:

                                                                V = V+1

                                                                V = V-1

                                                                IF V <> 0 GOTO L

                5.             NPDA                     Nondeterministic pushdown automata.

                6.             DPDA                     Deterministic pushdown automata.

                7.             CFG:                       Context-Free Grammar.

                8.             CFL:                        Context-Free Language.

                9.             E.R:                         Equivalence Relation.

              10.             DCFL:                     Deterministic CFL.

              11.             l:                             The empty-string.

              14.             ^:                             Conjunction operator. (AND)

              15.             +:                             Disjunction operator. (OR)

              16.             ~:                             Negation operator. (NOT)

              17.             ->:                           Implication operator (IMPLIES)

              21.             P,Q,R,S:                  A predicate (in Predicate Calculus)

              22.             A,B,C,D:                 A Literal   (in Propositional Calculus)

               

1.             Consider the following FSA with three states {q1,q2,q3) and two input symbols{a,b}:  

                                (only q3 is accepting)

 

State/input	a	b
q1	1	2
q2	3	2
q3	3	2

 

                Derive and clearly show the language accepted by the above FSA.

 

                        Solution:

·         Once you draw the transition graph, you can easily see that a^* b b^* a represents the set of all strings each of which makes this acceptor reach the lone accepting state q3 for the first time.

·         There are two loops for this acceptor to traverse from this accepting state q3 back to it. They are driven by the strings  a and  bb^*a.  

·         So, strings to be accepted by this acceptor are represented by the Regular Expression : a^* b b^* a (a + b b^* a)^*.

·         This expression contains strings such as:

o    ba

o    aba

o    abba

o    aabba

o    aabbba

o    aaabbba

o    aaabbbaaa

o    aaabbbbbbba

                       

2.             Prove or disprove that the following language is  Regular:

 

L₁ = { a^m bⁿ |  m,n >= 1}

L₂ = { a^m b^m |  m >= 1}

                       

Solution:

1.        L₁  is  regular as we can have a regular grammar that can generate the language as follows:

        S  ->  a  S

        S  ->  a  R

        R  ->  b  R

        R  ->  b 

2.        L₂  is not regular because (a) it is necessary that a substring of any sufficiently long string of this language  must pump both a’s and b’s so that the resulting longer strings will be in the language but (b) it is  impossible that in the resulting longer strings all pumped b’s appear before all a’s being pumped. Hence, the resulting longer strings cannot be in the same language.

 

         3.              Convert the following WFF to the CNF (Conjunctive Normal Form) and to the DNF (Disjunctive Normal Form),

                          respectively:

                F1:           (A+B+C) -> (D+E)

                F2:           ~(A^B^C -> D^E)

                F3:           (A^B)  ->  (C^D)

 

          Solution:

                F1:           ~A^~B^~C + (D+E) =  ~A^~B^~C +D+E

                               This is already in DNF with the following 3 fundamental conjunctions:

                                                ~A^~B^~C

                                                D

                                                E

                                Now, it is not in CNF yet. We need to apply a distribution law,

A^B+C = (A+C) ^ (B+C)

So, F1 becomes (~A^~B+D+E) ^ (~C+D+E).

Applying the same law one more time, we get

(~A^+D+E) ^ (~B+D+E) ^ (~C+D+E), which is in CNF with 3

fundamental disjunctions.

                (~A^+D+E)

                (~B^+D+E)

                (~C^+D+E)

                F2:           (A^B^C) ^  ~(D^E) =  (A^B^C) ^  (~D+~E)

                                =  A^B^C^(~D+~E) which is in CNF with the following

                                4 fundamental disjunctions:

                                                A

                                                B

                                                C

                                                ~D+~E

                                Now it is not in DFN yet. We need the other distribution law,

                                (A+B)^C = (A^C)+(B^C)

                                Applying this law, we get (A^B^C)^~D + (A^B^C)^~E

                                which is in DNF  with 2 fundamental conjunctions:

                                                A^B^C^~D

                                                A^B^C^~E

 

F3:           (A^B)  ->  (C^D)

                =  (~A+~B) + (C^D)  = ~A + ~B + (C^D) which already is in DNF.

                Clearly, this DNF has the following three fundamental conjunctions:

a.        ~A

b.        ~B

c.        C^D

Now, in order to get the CNF, we need to apply a distribution law to get needed conjunction(s) from the disjunctions we currently have, namely,  X+Y^Z = (X+Z)^(Y+Z). Applying this equivalence, we get

~A + ~B + (C^D) = (~A + ~B + C) ^ (~A + ~B + D) which is in CNF.

This CNF clearly has two fundamental disjunctions and they are:

a.        (~A + ~B + C)

b.        (~A + ~B + D)

c.         

        4.             Give a Regular grammar or a FSA for the following language:     L3 = (a + b)^* (c + d)⁺.

 

                                Solution:  Grammar:

                                                                S  ->  a S

                                                                S  ->  b S

                                                                S  ->  c  R

S  ->  d  R

R  ->  c  R  |  d  R  |  l   

 

                                                 FSA:      

State/input	a	b	c	d
q1	1	1	2	2
q2	3	3	2	2
q3	3	3	3	3

                                Only q2 is accepting. (q3: Dead state)

 

5.             Give a FSA that accepts the following regular language:

                        L3  =  {a^m bⁿc^k  |m,n,k >= 1}

                So, this language contains all strings that start with one or more a’s followed by one or

                more b’s followed by one or more c’s and nothing else. Of course, the number of a’s,

                the number of b’s and that of b’s do not have to be the same.        

                Solution:

State/input	a	b	c
q1	2	5	5
q2	2	3	5
q3	5	3	4
q4	5	5	4
q5	5	5	5

                                       

 

 

 

 

 

 

 

q4 is the only accepting state and q5 is a dead state that represents all failing

strings not to be accepted as they are not in the language.

 

6.              Give a FSA that accepts the following regular language:

                        L4  =  {a^m bⁿ  |m,n >= 1} 

                 This regular language is a bit simpler than L3 above.

                 Solution:

State/input	a	b
q1	2	4
q2	2	3
q3	4	3
q4	4	4

 

                                       

 

                                                       

 

        

                                q3 is the only accepting state.

                               

         7.                   

L6 = {a^m b^m c^m  |m >= 1}

                                L7 = {a^m bⁿ c^m |m,n>=1}

 

                        Prove or disprove that each language above is CF.

                                Solution:

 

                                L7 is CF as we have a CFG that can define it:

                                                S  ->  a  S  c  |  a  R  c

                                                R  ->  b  R  |   b  

 

                                L6 is not CF because while it is necessary for the two substrings of five into which

                                any sufficiently long string of this language can be decomposed to pump

all three symbols (a, b and c) so that resulting longer strings will have the same

number of a’s and b’s and c’s (in order  for them to be all in the language) the  two

substrings are not allowed to be that far away from each other according to one of

restrictions of the CFL Pumping Lemma.

 

        8.             List some applications of DFSA/Regular-Grammars/Regular-Expressions.     

 

                                a. Scanners of Compilers are a model of a DFSA.

                                b. ALU binary adders and binary multipliers.

                                c. FSA used in Network Communications Protocol (TCP Non-Halting FSA)

                                d. Regular expressions used in word editors including java string matching feature.

 

        9.             List some applications of CFG/CFL/NPDA.

a.        Compiler parser design such as Recursive Descent parsers.

b.        Specifying most syntax requirements of modern programming languages in use including

·         A certain language construct needs to appear before another in any program such as the declaration section needing to appear always before the execution/use section.

·         Allowing a list of any number of identical or similar items such as a list of any number of consecutive variables in one type declaration statement or any number of consecutive statements in a block or in a function/method or any number of operators in an expression.

·         Specifying operator precedence and operator associativity.

·         SNOBOL pattern definitions

·         PROLOG Clause specifications.

c.        CFG’s used as a design tool of unambiguous Language. 

d.        CFG’s used in Reverse Engineering.

                               

        10.           Capabilities of CFG

                                a. They can specify most syntax requirements of modern programming languages in use.

                                b. In particular, they can specify following language features:

·         A certain language construct needs to appear before another in any program such as the declaration section needing to appear always before the execution/use section.

·         Allowing a list of any number of identical or similar items such as a list of any number of consecutive variables in one type declaration statement or any number of consecutive statements in a block or in a function/method or any number of operators in an expression.

·         Specifying operator precedence and operator associativity:

EX1:   Exp  ->  Exp – Term

           (Depending on how the non-terminal Term is defined), above one rule is

           to make the  –  operator  left-associative.

EX2:   Exp  ->     Exp – Term   

           Term  ->  Term * Factor   

           Above two rules jointly together are to set the precedence of * operator

           above the   –  operator  so that A– B*C means A– (B*C).   ­­

                        c.  Although the CFG Ambiguity Problem is undecidable, many known unambiguous CFG’s

                             are used in algorithm design such as parsers and string generating algorithms and

                             SNOBOL Pattern definitions.  

 

11.           Give two wffs in CNF in propositional logic with at least three fundamental disjunctions.

                        Solutions:

a.        A ^ B ^ C                                : (3 fundamental disjunctions)

b.        A ^ B ^ ~C                             : (3 fundamental disjunctions)

c.        A ^ B ^ ~C ^ (D+E+~F)        : (4 fundamental disjunctions)

d.        A ^ (B+C+~D) ^ (~C+E) ^ F                : (4 fundamental disjunctions)

 

                Give two wffs in DNF in propositional logic with at least three fundamental conjunctions.

                        Solutions:

a.        A + B + C                                               : (3 fundamental conjunctions)

b.        A + B + ~C                                             : (3 fundamental conjunctions)

c.        A + B + ~C + (D^E^~F)                        : (4 fundamental conjunctions)

d.        A + (B^C^~D) + (~C^E) + F                                : (4 fundamental conjunctions)

e.        (A^~B) + (C^~D) + ~E + F + G           : (5 fundamental conjunctions)

 

 

 

        12.           Prove that either the Predicate HALT(x,y) or the Membership Problem for RE sets is Unsolvable.  

                        This Predicate is, of course, determines whether or not an arbitrary program y eventually

                        stops upon taking an input x.

 

                                Solution: 

HALT(x,y)

                                Assume that HALT(x,x) were solvable and hence Computable, that is, there is a program

                                in our SIMPLE language that computes this predicate which is a (special case of) function.

                                Now, consider the following program with just one instruction:

                                                 [A]  if  HALT(x,x)  GOTO A

                                Due to our assumption to the contrary that HALT(x,x) were Computable, above one-instruction

                                program can be regarded as a program strictly out of the three basic instructions of

                             our SIMPLE language and so by a certain encoding system, this program can be

                                represented uniquely by an integer, #p.

                                Now, consider HALT(x, #p). This is to ask if this program represented by

                                #p eventually stops upon taking an input x. We see that the answer to this

                                question is exactly the opposite of the answer to HALT(x,x).

                                That is,    HALT(x,#p) = ~(HALT(x,x)) which should be the case for any and all

                                possible values of x. If we substitute #p for x, we get

                                                HALT(#p,#p) = ~(HALT(#p,#p)) which is a downright contradiction.

                                This shows that HALT(x,x) is not Computable and neither is HALT(x,y).

                                So, HALT(x,y) is Unsolvable (Undecidable) by the Church Thesis. 

 

                                R.E. Membership Problem

                                This is to decide whether or not a given string is indeed a string of a given type-0 language.

                                As we believe that a type-0 language is accepted by a program

                                in the SIMPLE language (or equivalently by a Turing Machine program) by

stopping when a string is provided as the input to the program. So, the only time we can confirm that the input string indeed belongs to the language is when we can tell that the program indeed stops on that input string (or equivalently number). However, as HALT(x,y) is not computable, we cannot always tell if a program stops on a certain given input and this means that we cannot always tell if a string belongs to a given type-0  language in question.

 

      13.            List some Unsolvable problems.

                                Solution:

·         Membership Problem in type-0 (Recursively enumerable) languages.

·         HALT(x,y), deciding whether or not a program y ever stops on taking an input x.

·         Whether or not a program computes a total function (by stopping on any and all possible inputs, of course)

·         Whether or not a program stops on any one input at all.

·         Whether of not a type-0 grammar defines an infinite language.

·         Whether or not type-0 grammar defines an empty language.

·         Whether or not the language defined by a type-0 grammar contains all possible strings in it, that is, if it is the Universe Set.

·         CFG Ambiguity Problem, deciding whether or not a CFG is ambiguous.

·         Whether or not a CFL is deterministic.

·         Whether or not two CFG’s equivalent, namely if they define the same language.

  

      14.              Describe requirements of CNF (Chomsky Normal Form) and GNF (Greibach Normal Form)  for CFG.

                                Solution:

a.        CNF:  The righthand side string must be either just one terminal or exactly two nonterminals and nothing else.

b.        GNF:  The righthand side string must start with a terminal followed by zero or more nonterminals and nothing else.

For example,   N   ->   t                   // t is a terminal symbol.

                        N   ->   t  N₁            // N₁ is a nonterminal.

                        N   ->   t  N₁ N₂       // N₁ and N₂ each is a nonterminal. 

 

      15.             Explain why DCFL’s and CFL’s are not equivalent (or not the same)

                                Solution:

                                Because there are some CFL’s that cannot be accepted by a deterministic PDA due to

                                limited capabilities/resources of PDA’s.

Examples of these languages include:

·         L =  {w w^R where w is in {a,b}⁺ }  So, strings like  aa, bb, abba, abbbba, bbaabb and bbbaaaabbb are all in this language.

·         L =  {a^m b^m cⁿ  | m,n >=1} + {a^m bⁿ cⁿ  | m,n >=1}

·         L =  {a^m b^m cⁿ  | m,n >=1} + {a^m bⁿ c^m  | m,n >=1}

 

16.             Explain why deterministic FSA’a and nonterministic FSA’a are equivalent.

                          Solution:

·         FSA’a become (truly) nondeterministic only due to two reasons: (a) there are empty-transition(s) in a FSA or (b) there are multiple transitions defined on the same combination of a current state and a current input symbol in a FSA.

·         The first reason of “Empty-transitions can be systematically removed by an algorithm which computes and uses the Empty-Closure of each existing state.

·         The second reason of “Multiple transitions” can be systematically converted into a unit (only one) transition instead by regarding a state as a combination of all possible next states indicated by all multiple transitions being involved.

 

      17.              Convert the following CFG into the CNF and clearly show the result:

                                                S   ->   S  R

                                                S   ->   ( P  R ) 

                                                P   ->   (  R  )

                                                R   ->   (  )

                                Solution:

1.        We need to introduce a nonterminal for each terminal of this grammar to start with

which will derive nothing but the associated terminal .

So,  we  need following rules to be added to this grammar among others:

     Left    ->  (

     Right  ->  ) 

2.        Next, we pick up every existing rule not allowed by CNF.

Every rule except the first one is against the CNF.

a.        S   ->   ( P  R ) 

                                                    S     ->  Left  S1

                                                    S1   ->  P  S2

                                                    S2   ->  R  Right

b.        P   ->   (  R  )  

    P     ->   Left  S2 

c.        R   ->   (  )

    R     ->   Left  Right  

3.        Final Grammar: 

    S     ->  S   R

                                                    S     ->  Left  S1

                                                    S1   ->  P  S2

                                                    S2   ->  R  Right 

    P     ->   Left  S2 

    R     ->   Left  Right

    Left    ->  (

    Right  ->  )