Scribd
Upload
22 views1 page

Theoretical Computer Science Q&A Guide

The document contains solved questions and detailed answers related to theoretical computer science topics, including regular expressions, the Pumping Lemma, ambiguous grammar, Greibach Normal Form, operations on languages, nullable symbols in context-free grammars, and finite automata. Key concepts such as the smallest string accepted by a regular expression and the characteristics of deterministic finite automata (DFA) are discussed. The document serves as a study guide for understanding fundamental principles in theoretical computer science.

Uploaded by

sonuchaure548
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
22 views1 page

Theoretical Computer Science Q&A Guide

The document contains solved questions and detailed answers related to theoretical computer science topics, including regular expressions, the Pumping Lemma, ambiguous grammar, Greibach Normal Form, operations on languages, nullable symbols in context-free grammars, and finite automata. Key concepts such as the smallest string accepted by a regular expression and the characteristics of deterministic finite automata (DFA) are discussed. The document serves as a study guide for understanding fundamental principles in theoretical computer science.

Uploaded by

sonuchaure548
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

Theoretical Computer

Science - Solved and


Detailed Answers
Q1. Attempt any Eight of the
following (out of Ten):

a) Smallest string accepted by


(ab*|b)ab*

The regular expression (ab*|b)ab*


accepts strings starting with either:

an 'a' followed by zero or more 'b's,


or
a single 'b'

and then followed by zero or more 'b's.


Smallest accepted string: "a" (when we
choose "a" from the first part and zero
b’s).

b) True or False: Pumping Lemma is


used to show that language is not
regular.

True. The Pumping Lemma helps prove


that certain languages are not regular by
showing that no matter how you divide a
sufficiently long string into parts (x, y, z),
repeating the middle part 'y' any number
of times results in a string not in the
language.

c) Define Ambiguous Grammar

A grammar is said to be ambiguous if


there exists at least one string that can
have more than one distinct leftmost
derivation tree (parse tree).
Example:

E → E + E | E * E | id

For the expression id + id * id , there


are two parse trees — one for (id + id)
* id and another for id + (id * id) .

d) Define GNF (Greibach Normal


Form)

A context-free grammar is in Greibach


Normal Form (GNF) if every production is
of the form: A → aα , where 'a' is a
terminal and α is a string of non-terminals
(possibly empty).

GNF is important in parsing and automata


theory as it ensures that each step of
derivation introduces exactly one terminal
symbol.

e) Two operations on languages

Union (L1 ∪ L2): All strings that are


in L1 or L2.
Concatenation (L1L2): Strings
formed by taking a string from L1
followed by one from L2.

f) Find nullable symbols in CFG

Given CFG:

S → AB | aBb
A → aA | ε
B → AD | aAb
D → bD | ε

Nullable symbols are those that can


derive ε.

A → ε ⇒ A is nullable
D → ε ⇒ D is nullable
B → AD: since A and D are nullable
⇒ B is nullable

Answer: A, B, D

g) Diagrammatic representation of
TM

TM Diagram

h) Write RE for A = { ab, aabb,


aaabbb... }

This is the language where number of a’s


= number of b’s and all a’s come first:
L = { aⁿbⁿ | n ≥ 1 }
This is a context-free language and not
regular. Hence, no valid regular
expression exists.

i) Describe FA from diagram

The FA accepts strings that contain


exactly two 1's. It starts from q0 and
moves through transitions labeled '1'. It
reaches final state q3 only after two 1’s
have been read, regardless of the number
of 0’s.

j) DFA cannot have more than one


final state. True or False?

False. A DFA can have multiple final


states. Any state can be designated as
final depending on which strings you want
the DFA to accept.

You might also like