KEMBAR78
Assignment 1 TOA | PDF
Scribd
Upload
79 views1 page

Assignment 1 TOA

This document contains 7 questions about formal languages and automata theory assigned over 1 week. The questions cover topics from chapters 2-4 including: the number of words of a given length in a language, recursive definitions of languages, constructing regular expressions for specific languages, and showing equivalence of regular expressions.

Uploaded by

MUHAMMAD UMER
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
79 views1 page

Assignment 1 TOA

This document contains 7 questions about formal languages and automata theory assigned over 1 week. The questions cover topics from chapters 2-4 including: the number of words of a given length in a language, recursive definitions of languages, constructing regular expressions for specific languages, and showing equivalence of regular expressions.

Uploaded by

MUHAMMAD UMER
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Assignment: 01

THEORY OF AUTOMATA & FORMAL LANGUAGES Marks =10 Time: 01 week

Q1: Consider the language S*, where S = {a, b}. How many words does this
language have of length 2? of length 3? of length n? (Chapter 2)

Q2: Consider the language S*, where S = {aa, b}. How many words does this
language have of length 4? of length 5? of length 6? What can be said in
general? (Chapter 2)

Q3: Consider the language S* where S = {xx xxx}. In how many ways can x"9 be
written as the product of words in S? This means: How many different
factorizations are there of x19 into xx and xxx? (Chapter 2)

Q4: Show that the following is another recursive definition of the set EVEN.
Rule 1: 2 and 4 are in EVEN.
Rule 2 If x is in EVEN, then so is x + 4. (Chapter 3)

Q5: Give a recursive definition for the language S* where S = {aa,b} (Chapter 3)

Q6: Construct a regular expression defining each of the following languages


over the alphabet I = {a, b}.
1. All words in which a appears tripled, if at all. This means that every
clump of a's contains 3 or 6 or 9 or 12... a's.
2. All words that contain exactly three b's in total.
3. All strings that end in a double letter. (Chapter 4)

Q7: Show that the following pairs of regular expressions define the same
language over the alphabet I = {a, b}.
(i) (ab)*a and a(ba)*
(ii) (a* + b)* and (a + b)*
(iii) (a* + b*)* and (a + b)* (Chapter 4)

You might also like