Scribd
Upload
204 views

Group Assignment - Formal Language Theory

The document contains a group assignment submitted by four computer science students at Admire University Bishoftu Campus. It includes instructions for the assignment such as submitting answers in MS Word or PDF format via Telegram by a deadline of June 25, 2020. It also lists three questions about formal language theory: explaining phrase structure grammar and its types with examples; explaining grammar derivation and its types with examples; and explaining deterministic and non-deterministic finite automata with examples.

Uploaded by

hak adv
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
204 views

Group Assignment - Formal Language Theory

The document contains a group assignment submitted by four computer science students at Admire University Bishoftu Campus. It includes instructions for the assignment such as submitting answers in MS Word or PDF format via Telegram by a deadline of June 25, 2020. It also lists three questions about formal language theory: explaining phrase structure grammar and its types with examples; explaining grammar derivation and its types with examples; and explaining deterministic and non-deterministic finite automata with examples.

Uploaded by

hak adv
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/ 8

ADMAS UNIVERSITY BISHOFTU CAMPUS

Course Title -Formal Language Theory


TITLE: GROUP ASSIGNMENT I1

GROUP MEMBERS
S.No NAME ID SECTION YEAR DEPT.

1 HABTAMU H/MICHAEL 0500/17 1 3RD CoSc

2 GADISA NEGASO 0194/17 1 3RD CoSc

3 KASSAHUN TAFESE 0192/17 1 3RD CoSc

4 SEFELEGE TEREFE 0211/17 1 3RD CoSc

Submitted to Instructor: Fikre T.


June 02, 2020 G.C.
INSTRUCTIONS
NB: Read duly the following instructions and act as per requirements.
o This is a group assignment. Thus, copy and paste from other groups will result in
zero values.
o You must use either MS-word or PDF format for your answers. Other forms may
not to be welcomed. In particular images using cell phone be considered at your
risk.
o You must send your work using telegram via cell phone: 0961-95-17-33 only using
private telegram account for telegram users are welcomed. You cannot send via
your (students) group telegram.
o Otherwise non- telegram user may submit in person using hardcopy to your
respective department. Those who are willing to submit with hardcopy should
make sure that their handwriting is legible. Please any other way of submission is
not welcomed.
o Your final submission date is on June 25/06/2020. You can submit before the due
date. I highly value your punctuality as part of your assignment. Thus, late
submission may result in 1% punishment per delay for each day. But the
submission date by no means extends beyond June 27/06/2020.
o Neatness and clarity have its own value!
Stay Safe!

QUESTIONS:
1. Briefly explain phrase structure grammar and the different types with example?
2. Briefly explain derivation of grammar and the different types with example?
3. Briefly explain deterministic and non-deterministic finite state automata with
example?
1. Briefly explain phrase structure grammar and the
different types with example?
phrase structure grammars are all those grammars that are based on the
constituency relation, as opposed to the dependency relation associated
with dependency grammars; hence, phrase structure grammars are also
known as constituency grammars

Type - 0 Grammar: -

➢ Type-0 grammars generate recursively enumerable languages. The


productions have no restrictions. They are any phase structure
grammar including all formal grammars.

➢ The productions can be in the form of α → β where α is a string of


terminals and non-terminals with at least one non-terminal
and α cannot be null. β is a string of terminals and non-terminals.
o Example
S → ACaB
Bc → acB
CB → DB
aD → Db
Type - 1 Grammar
➢ Type-1 grammars generate context-sensitive languages. The productions
must be in the form
αAβ→αγβ

o Example
AB → AbBc
A → bcA
B→b
Type - 2 Grammar
➢ Type-2 grammars generate context-free languages
The productions must be in the form A → γ
where A ∈ N (Non terminal)
and γ ∈ (T ∈ N)* (String of terminals and non-terminals).
✓ These languages generated by these grammars are be recognized by a non-
deterministic pushdown automaton.
o Example
S→Xa
X→a
X → aX
X → abc
X→ε

Type - 3 Grammar
➢ Type-3 grammars generate regular languages. Type-3 grammars must
have a single non-terminal on the left-hand side and a right-hand side
consisting of a single terminal or single terminal followed by a single non-
terminal.
The productions must be in the form X → a or X → aY
where X, Y ∈ N (Non terminal) and a ∈ T (Terminal)
✓ The rule S → ε is allowed if S does not appear on the right side of any rule.
o Example
X→ε
X → a | aY
Y→b

Grammar Type Grammar Language Accepted Automaton


Accepted

Type 0 Unrestricted Recursively Turing Machine


grammar enumerable language

Type 1 Context-sensitive Context-sensitive Linear-bounded


grammar language automaton

Type 2 Context-free Context-free language Push down


grammar automaton

Type 3 Regular grammar Regular language Finite state


automaton

2. Briefly explain derivation of grammar and the different


types with example?
Derivation
➢ Derivation is a sequence of production rules. It is used to get the input string
through these production rules. During parsing, we have to take two decisions.
These are as follows:

❖ We have to decide the non-terminal which is to be replaced.


❖ We have to decide the production rule by which the non-terminal will be replaced.

We have two options to decide which non-terminal to be placed with production rule.

1. Leftmost Derivation:

In the leftmost derivation, the input is scanned and replaced with the production rule
from left to right. So in leftmost derivation, we read the input string from left to right.

Example:

Production rules:

E=E+E
E=E-E
E=a|b

Input

a-b+a

The leftmost derivation is:

E=E+E
E=E-E+E
E=a-E+E
E=a-b+E
E=a-b+a

2. Rightmost Derivation:
In rightmost derivation, the input is scanned and replaced with the production rule
from right to left. So in rightmost derivation, we read the input string from right to left.

o Example

Production rules:
E=E+E
E=E-E
E=a|b

Input

a-b+a

The rightmost derivation is:

E=E-E
E=E-E+E
E=E-E+a
E=E-b+a
E=a-b+a

When we use the leftmost derivation or rightmost derivation, we may get the same
string. This type of derivation does not affect on getting of a string.

Example of Derivation:
Derive the string "abb" for leftmost derivation and rightmost derivation using a CFG
given by,

S → AB | ε
A → aB
B → Sb

Solution:

Leftmost derivation:
Rightmost derivation:

3. Briefly explain deterministic and non-deterministic


finite state automata with example?

3.1 Deterministic Finite Automata (DFA)


➢ DFA consists of 5 tuples {Q, Σ, q, F, δ}.
➢ Q : set of all states.
➢ Σ : set of input symbols. ( Symbols which machine takes as input )
➢ q : Initial state. ( Starting state of a machine )
➢ F : set of final state.
➢ δ : Transition Function, defined as δ : Q X Σ --> Q.

In a DFA, for a particular input character, the machine goes to one state only. A
transition function is defined on every state for every input symbol. Also in DFA null (or
ε) move is not allowed, i.e., DFA cannot change state without any input character.

For example, below DFA with Σ = {0, 1} accepts all strings ending with 0.
One important thing to note is, there can be many possible DFAs for a pattern. A DFA with
minimum number of states is generally preferred.

3.2 Non-deterministic Finite Automata (NFA)


NFA is similar to DFA except following additional features:

1. Null (or ε) move is allowed i.e., it can move forward without reading symbols.
2. Ability to transmit to any number of states for a particular input.
However, these above features don’t add any power to NFA. If we compare both in
terms of power, both are equivalent.

Due to above additional features, NFA has a different transition function, rest is
same as DFA.

δ: Transition Function

δ: Q X (Σ U ε ) --> 2 ^ Q.

As you can see in transition function is for any input including null (or ε), NFA can go to
any state number of states.
For example, below is a NFA for above problem

You might also like