cs402 5 Theory of Automata (CS402) Assignment Solution

Theory of Automata (CS402)

Assignment No.5

Deadline

Your assignment must be uploaded before or on.

Rules for Marking

It should be clear that your assignment will not get any credit if:

·         The assignment is submitted after due date

·         The assignment is copied

Objectives

Objective of this assignment is to make you able to understand the following concepts,

·         Defining Context Free Grammars for Different Languages

·         Null and Null-able Transitions and Regular Context Free Grammars

·         Chomsky Normal Form

·         Push Down Automata

Question No.1

Give CFG for the following languages,

1. aⁿb^m where n = m-1 and n = 1,2,3…

Some words belonging to this language are, a ,  aab , aaabb , aaaabbb , ….

∑ = {a,b}

S à aX

X à aXb | ab | Λ

2. aⁿb²ⁿ where n = 1,2,3…

Some words belonging to this language are, abb ,  aabbbb , aaabbbbbb , ….

∑ = {a,b}

S à aSbb

S à abb 

S à Λ

Question No.2

Consider the CFG given below and find Null and Null-able transitions (if any) also remove these transitions to give new CFG

S ---- > ABB | CC | ABC | AC

A --- > a | Є

B --- > b | C

C --- > ab | Є

[Here Є means null string, as in CFG’s we use Є for indicating null string instead of ^ sign]

Solution:

   

      S à ABB | BB | CC | C | ABC | AB | BC | AC | A | C

     A à a

     B à b | C

     C à ab      

Question No.3

Convert the CFG (Context Free Grammar) given below to CNF (Chomsky Normal Form)

S ---- > YYY | ZZ | aa | bb

Y --- > a | Z

Z --- > b | Y

Solution:

S à RY | ZZ | YZ | ZY

R à YY

Y à a | Z

Z à b | Y

Question No.4

Design PDA (Push Down Automata) for the language given below,

(ba)ⁿ(a)ⁿ                  n = 1,2,3…

cs402 gdb theory of automata fall 2012

A regular expression is an expression that explains a pattern for a string. A string matches a regular expression if that string follows the pattern of that regular expression. In computing, a regular expression provides a concise and flexible means for "matching" (specifying and recognizing) strings of text, such as particular characters, words, or patterns of characters.

Compiler constructor is a process of creating a compiler. Compiler is a computer program that translates the high level language source code into low level language. Compiler construction is a complex process that is divided into different phases like front end, middle end and back end.

Regular expressions are used in front end phase in the lexical analysis. In this phase the source code is break down into small pieces called tokens. Finite state automation is used to recognized tokens and it is constructed from regular expressions.

Regular expressions are used by many text editors, utilities, and programming languages to search and manipulate text based on patterns. Some of these languages, including Perl, Ruby, AWK, and Tcl, integrate regular expressions into the syntax of the core language itself. Other programming languages like .NET languages, Java, and Python instead provide regular expressions through standard libraries. 

CS402 4 Theory of Automata assignment solution fall january 2012

Question No 1

Marks: (2.5*4) =10 

Recall the idea of regular languages, so if L1 and L2 are regular languages then L1 + L2 , L1L2 and L1* are also regular languages. If L1 and L2 are expressed by TG1 and TG2 given below then find:

       I.      L1 + L2

    II.      L1L2

 III.      L1*

  IV.      L2^C

 

CS402 theory of automata quizes

1. Two languages are said to belong to same class if they C when they run over an FA, that state  (May befinal State or not).
2. One language can have ……… CFG(s) (At least one)
3. If an FA has N state then it must accept the word of length (n+1)
4. In pumping lemma theorem (x y^n z) the range of n is (1,2,3,4,………)
5. For a non regular language there exist …… FA (NO)
6. If the intersection of two regular languages is regular then the complement of the intersection of these twolanguages is also regular (True)
7. According to Myhill Nerode theorem, if L generates finite no. of classes then L is.......(Regular)
8. The language generated by the CFG is called the language ……by the CFG (Produced) 
9. If L1 and L2 are regular languages then which statement is NOT true? (L1/L2 is always regular)
10. The values of input (say a & b) does not remain same in one cycle due to (clock pulse)
11. The reverse of the string sbfsbb over { sb, f, b } (bsbfsb)
12. In CFG, the symbols that cannot be replaced by anything are called Terminals
13. a^n b^n generates the ………… language (Non regular languages)
14. The production S --> SS | a | b | ^ can be expressed by RE (a+b)+
Any word generated by given CFG can also be expressed by (Syntax tree or Generation
tree or Derivation tree as well)
15. Set of all palindromes over {a,b}is regular (false)
16. The grammatical rules which involves meaning of words are called: (semantic)
17. An FA has same initial and final state, then it means that it has no final state. (false)
18. The same non terminals can be written in single line if they have more than one..........(Productions)
19. In pref(Q in R) Q is …… to (than) R (Q is not equal to R)
20. The complement of a regular language is also a regular (True)
21. There is at least one production that has one........on its left side. (None Terminal)
22. For language L defined over {a, b},then L partitions {a, b}* into …… classes (Distinct) 

CS402 3 Theory of Automata assignment solution fall December 2011

Total Marks= 20 (5+5+5+5)

Question No.1

1. Convert Moore machine given below in corresponding Mealy machine.

1. Run strin abbbba on this machine and corresponding Mealy machine by showing complete process and confirm that both machines generate same outputs (ignoring extra character of Moore machine).

Input		a	b	b	b	b	a
Status	qo	q1	q4	q4	q4	q4	q4
Moore	0	0	0	0	0	0	0
Mealy		0	0	0	0	0	0

Question No.2

1. Convert following Mealy machine into corresponding Moore machine.

1. Run string bbaaba on this machine and corresponding Moore machine by showing complete process and confirm that both machines generate same outputs (ignoring extra character of Moore machine).

Input		b	b	a	a	b	a
Status	qo	q3	q3	q3	q3	q3	q3
Mealy		1	1	1	1	1	1
Moore	1	1	1	1	1	1	1

CS402 Theory of Automata midterm solved past paper fall 26 November 2011

1.       What is difference between S+ and S*.

2.       What are Distinguishable strings and Indistinguishable strings?

3.       Is the moore machine is Distinguishable or Indistinguishable? Is the number of states remained constant if we convert moore machine to mealy machine discuss if any case?

4.       Write the first step to convert a TG into RE?
    Convert the following FAs to NFAs?
        a).

5.   Solution:

        b).S

   Solution:

   

CS402 assignment no. 1 solution fall 2011 soon

Theory of Automata

CS402

ASSIGNMENT NO.1

Total Marks= 20 (4+4+4+4+4)

Assignment Submission Deadline

Your assignment must be uploaded before or on 31-10-2011 [upload your assignment well before due date to avoid any assignment uploading related issues]

Rules for Marking

It should be clear that your assignment will not get any credit if:

• The assignment is submitted after due date
• The assignment is copied

Objectives

Objectives of this assignment are to make students able to understand the following concepts,

• Basic concepts clarification
• Recursive Definition of a language
• Regular Expression
• Finite Automata

Question No.1 Basic Concepts [Sets, Letters, Valid Alphabet, Languages, Strings and Words]

a. Which of the following are strings generated from alphabet Σ = {a, b}

                     i.            abba

                   ii.            baa$a

                  iii.            abc.

                 iv.            ba?

                   v.            b.bba

b. Which of the following are valid words for language of all strings ending with bab defined for alphabet Σ = {a, c ,  bab}

                     i.            acccba

                   ii.            cccbaa

                  iii.            cccbab

                 iv.            babbb

                   v.            baaab

Question No.2 Defining Languages [Using Recursive Definition, Re’s, Fa’s]

Give recursive definitions of following languages defined over alphabet Σ = {a, b}

1. Having all strings starting with b and having length greater than 2
2. NOT having ab at any place.

Question No.3 Regular Expressions

Give Regular Expression for each of the following language defined over alphabet Σ = {a, b}

1. Even Length strings ending with b

2. Strings with b’s count multiple of three

Question No.4 Models To Recognize Languages (Fa’s)

Give Finite Automata (FA) for each of the following language defined over alphabet Σ = {a, b}

1. Language having all strings NOT containing aa at any place
2. Language of all strings NOT STARTING with bb

Question No.5 Models To Recognize Languages (Nfa’s)

Give Non Deterministic Finite Automata (NFA) for each of the following language defined over alphabet Σ = {a, b}

1. Language of all strings STARTING WITH bba
2. Language having all strings NOT having even no of a’s and b’s

You can view the demo video in file,http://vulms.vu.edu.pk/Courses/CS402/Downloads/Assignment1.00.zip to see how to make FA in MS Word.

Note:

Please keep in view the following points while attempting any question:

• Where OR is used in the description of a language it means that expressions on both sides of ‘OR’ are parts of the language.
• Where NOT is used in the description of the language it means that language includes all strings except described in the ‘NOT’ condition, for example language NOT starting with a, means all strings not having a in the start (you have to evaluate yourself what kinds of strings are these).

Assignment Uploading Instructions:

• Upload single word file having solutions for all parts as well as chart images.

• You can crop and compress images in the word file by double clicking on an image and selecting compress all images option to decrease file size before uploading it.

Appendix:

Definition of Set:

A set can be defined as follows:

“Non repeating collection of elements”

Example Sets:

1. {car, bus }
2. {table, chair , stand}
3. {basket ,eggs}
4. { ^, #, *, / }

However {car, car, bus} is NOT a set according to its definition.