KEMBAR78
Tutorial Sheet Tafl Unit 2 | PDF | Automata Theory | Formalism (Deductive)
Scribd
Upload
50 views2 pages

Tutorial Sheet Tafl Unit 2

This tutorial sheet for B. Tech CSE outlines the course details for TAFL BCS-402 in the 4th semester, including the course coordinator and learning outcomes. It contains short and long answer type questions related to formal languages, automata theory, and regular expressions. Additionally, it lists references for textbooks relevant to the subject.

Uploaded by

movite6018
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
50 views2 pages

Tutorial Sheet Tafl Unit 2

This tutorial sheet for B. Tech CSE outlines the course details for TAFL BCS-402 in the 4th semester, including the course coordinator and learning outcomes. It contains short and long answer type questions related to formal languages, automata theory, and regular expressions. Additionally, it lists references for textbooks relevant to the subject.

Uploaded by

movite6018
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/ 2

Tutorial Sheet-2

Program B. Tech CSE


Session 2024-25
Subject Name with Code TAFL BCS-402
Year & Semester 4th semester
Unit No. 2
Date of Distribution 22/04/2025
Name of Course Coordinator/Faculty Mr. Chinmay Shukla
Course Outcome(CO1) Analyse and design turing machine, formal
languages, grammers.

Short Answer Type Questions:

Q Question Description BL MM
1. Define a regular expression over the alphabet Σ={a,b}Σ={a,b} for the
language consisting of all strings that start with 'a' and end with 'b'. List three 2
4
1 strings that belong to this language and two that do not.

1.
Given the regular expressions r1=a+br1=a+b and r2=ab+ba+br2=ab+ba+b,
a) Find a string that is accepted by r2r2 but not by r1r1.
4 2
2 b) Find a string that is accepted by both r1r1 and r2r2.

1. What is Kleene’s Theorem? State its significance in the context of regular 6


languages and finite automata. 2
3
1. Construct a finite automaton (FA) for the regular expression (a+b)∗(a+b)∗.

4 Draw the transition graph and list the set of states, alphabet, start state, set of 6 2
accepting states, and the transition function.

1.
Given the following system of equations derived from a finite automaton:
q1=q10+ϵq1=q10+ϵ
q2=q11+q20q2=q11+q20
5 6 2
Use Arden’s Theorem to find the regular expression corresponding to the
language accepted by the automaton.

Long Answer Type Questions:

6 1. Explain the algebraic method using Arden’s Theorem for converting a finite 4 4
automaton into a regular expression. Illustrate your answer with a simple
example.
7 Prove or disprove: The language L={anbn∣n≥0}L={anbn∣n≥0} is regular. 4 4
Justify your answer using the Pumping Lemma.

List and explain the closure properties of regular languages. Give an example
8 6 4
of each property (union, concatenation, and Kleene star).

1. What is the Pigeonhole Principle? How is it used in the context of regular


9 languages to prove non-regularity? 6 4

1. Define decidability in the context of finite automata and regular languages.


Give an example of a decision property for regular languages and explain how
10 6 4
it is determined.

REFERENCES

TEXT BOOKS:
Ref. Authors Book Title Publisher/Press Edition &Year
[ID of Publication
]
Introduction to
J.E.Hopcraft, Automata theory,
[T1] R.Motwani, Languages and Pearson Education Asia
and Ullman. Computation, 2nd
edition,
Introduction to
languages and the
[T2] J Martin, theory of Tata McGraw Hill
computation, 3rd
Edition,

Faculty Signature HOD Signature

You might also like