Factor Integrante

CHAPTER 1-EXERCISES

1.

      Build FAs with JFLAP that accept the following languages:

1. The language over  Σ ={a, b} of any even number of a’s and odd number of  b’ s.
2. The language over Σ ={a ,b} of any even number of a’s and at least  three b’s.

2.

      We present here a series of FAs where the author of each FA has made an incorrect claim about the language it recognizes. For each   FA , we list the file name where the FA is stored and the claimed language but are not accepted by FA you must :

(i) Produce six strings that are either in the indicated language but are not accepted by the FA , or that are accepted by the  FA , or that are accepted by the FA and are not in the language : simulate these strings on the FAs  as well.

(ii) Modify the FA so that it actually recognizes the language we claim it does.

(iii) Simulate those six strings again to show that they are now either accepted or rejected if they either are or are not in the language respectively.

It helps to use the fast simulator so that your test strings are saved form (i) to (iii).

1. The FA in ex1.6a recognizes the language of any string over the alphabet Σ ={a, b} with exactly two b’s.
2. The FA in ex1.6b recognizes the language of any strings of a’s of some  length divisible by 2 or 3.
3.  The FA in ex1.6c recognizes  the language of any string over the alphabet  Σ ={a, b, c}  with at least 3 b’s or at least  3 c’s.
4. The FA in ex1.6d recognizes  the language of any string over the alphabet Σ ={a, b, c} with at least 2 b’s or at least 3 c’s .

3.

     We present here a series of FAs. We then describe the language we want the FA to recognize. You must describe the changes necessary to make the FA recognize  the desired language . Edit the FA to make these modifications in JFLAP , and run several simulations of strings in ( and out) of the language to determine if they are accepted or rejected.

1. The FA in ex 1.6e accepts the language of any odd number of a’s. We  want the language of any even number of a’s.
2. The FA in ex1.1a accepts the language of any number of a’s  followed by any odd number of b’s . We want the language of any nonzero number of a’s followed by any odd number of b’s.
3.  The FA in ex1.6f accepts the language over Σ  ={a, b, c} of a followed by any odd number of b’s  followed by c, repeated any number of times. We  now want instead the Fa where instead of one c, there can be any even number of c’s .
4. Now , we want the DFA that accepts the language of Exercise 3c!

CHAPTER 3 -EXERCISES

1.

    Create right-linear grammars that generate the  following languages .Hint Test  input strings that should be accepted and rejected .

1. Σ = {a, b} .The language is strings with an even number  of a’s that have exactly one b. For example , accepted strings include aba , b, and aaaba , and rejected strings include abab and aaab.
2. Σ ={a , b}. The language is strings with an even number of a’s followed by three or fewer b’s . For example , accepted strings include aab , bbb ,aaabb and aaaa , and rejected strings include aabaab.
3. Σ ={a, b} .The language is string in which each b cannot be adjacent to another b. For example , accepted strings  include aba ,b, aabaaabaa , and baaaba , and rejected include aababa and babb.
4. Σ ={a, b} .The language  is strings in which the number of a’s is a multiple of three. For example  , accepted strings include ababa ,bb ,aaa, and aababb and rejected strings include aababa and aaaaba.

1. Σ ={a ,b} .The language is strings in which every a must have a b adjacent to it on both sides .For example  ,accepted strings include bababab ,bab, bbab , and babbbabb, and rejected strings include abab and baab.
2. Σ ={a, b} The language is strings in which every other a starting with the first a must immediately be followed by a b. For example accepted , strings include babaab , bab , abaabbabab and abbaab and rejected strings include ababa and aab.

2.

   The collegiate parasite Carl S .Student wants his parents to buy him a car . His father produces a “ transcripts string” of all the grades Carl has ever received in his entire life an arbitrarily long single string made up of symbols from Σ  ={ a, b, c, d, e, f} in no particular order .An a is a high grade and an f is failure . His father produces a simple criterion: if Carl received fewer than four d grades , he shall get a car , otherwise he shall not . An f grade counts as single  d grade.

...