Toa Ass3 Final

Kinnaird College for Women, Lahore
Post-Mid Assignment No. 3

Submitted to: Miss Rabeeya Saleem
Submitted by: Maria Imran
Roll Number: F21BSCS009
Subject: Theory of Automata
Section: A
Major: Computer Science
Q1. Write down about different levels of Chomsky Hierarchy. Also, provide
the detailed description of each level with demonstration of levels.
Chomsky's hierarchy is a classification system that categorizes formal grammars and languages
into four distinct levels. These levels are known as Type-0, Type-1, Type-2, and Type-3, each
representing a different level of complexity and generative power. Let's go through each level
with their detailed descriptions and examples:
1. Type-0: Unrestricted Phrase-Structure Grammar (Recursively Enumerable
Languages):
Type-0 grammars generate languages known as recursively enumerable languages. These
languages can be described by Turing machines and have no limitations on the rules or
restrictions on the production of symbols. They can generate any computable language.
Type-0 grammars are the most powerful and complex in the Chomsky hierarchy.
Example:
 S → aSb
 S→ε
In this example, the grammar allows the production of strings where the number of 'a's is
the same as the number of 'b's.
2. Type-1: Context-Sensitive Grammar (Context-Sensitive Languages):
Type-1 grammars generate languages known as context-sensitive languages. In these
grammars, the rules have specific constraints on the form of production rules, where the
left-hand side can be expanded or rewritten as the right-hand side while considering the
surrounding context. The context-sensitive languages can be recognized by linear-
bounded automata.
Example:
 αAβ → αγβ
In this example, the production rule allows the non-terminal symbol A to be replaced by γ
only when it appears in the context of α and β.
3. Type-2: Context-Free Grammar (Context-Free Languages):
Type-2 grammars generate languages known as context-free languages. In context-free
grammars, the left-hand side of the production rules consists of a single non-terminal
symbol that can be replaced by a string of symbols, regardless of the context. Context-
free languages can be recognized by pushdown automata.
Example:
 S → aSb
 S→ε
This grammar generates strings where any number of 'a's can be followed by the same
number of 'b's.
4. Type-3: Regular Grammar (Regular Languages):
Type-3 grammars generate languages known as regular languages. Regular grammars
have the simplest form, where the production rules are limited to a single non-terminal
symbol on the left-hand side and a regular expression on the right-hand side. Regular
languages can be recognized by finite-state automata.
Example:
 S → aS
 S→b
This grammar generates strings consisting of any number of 'a's followed by a single 'b'.
Each level in the Chomsky hierarchy represents a different class of languages with varying levels of
complexity and generative power. As we move from Type-3 to Type-0, the grammars become more
expressive but also more complex to work with.
Q2. Provide a detailed comparison of different types of machine in theory of

automata.
Here's a detailed comparison of these machine types:
1. NFA (Non-deterministic Finite Automaton):
An NFA is a mathematical model that consists of a finite set of states, an input alphabet, a
transition function, a start state, and a set of accepting states.
 Transition Function: In an NFA, the transition function allows multiple possible next
states for a given input symbol and current state. It can also have null transitions,
which allow transitions without consuming any input symbol.
 Acceptance: An NFA accepts a string if there exists any path from the start state to
an accepting state that can read the entire input.
 Representation: NFA is typically represented using a state transition table or a state
transition diagram.
 Complexity: NFA can have exponential time complexity for some input strings.
2. DFA (Deterministic Finite Automaton):
A DFA is a mathematical model that consists of a finite set of states, an input alphabet, a
transition function, a start state, and a set of accepting states.
 Transition Function: In a DFA, the transition function specifies a unique next state
for every input symbol and current state.
 Acceptance: A DFA accepts a string if there exists a unique path from the start
state to an accepting state that can read the entire input.
 Representation: DFA is typically represented using a state transition table or a
state transition diagram.
 Complexity: DFA has linear time complexity for any input string.
3. PDA (Pushdown Automaton):
A PDA is an extension of the DFA with an added stack that provides additional memory.
 Transition Function: The transition function of a PDA depends not only on the
current state and input symbol but also on the symbol popped from the stack. It
allows pushing and popping symbols from the stack during transitions.
 Acceptance: A PDA can accept strings based on either final state or empty stack
condition.
 Representation: PDA is typically represented using a state transition table or a
state transition diagram, along with the stack operations.
 Complexity: PDA can recognize context-free languages, which are more powerful
than regular languages recognized by DFA or NFA.
4. Moore Machine:
Definition: A Moore machine is a finite state machine in which the outputs are associated
with the states.
 Output Function: In a Moore machine, the output is determined solely by the
current state and does not depend on the input symbols.
 Transition Function: The transition function specifies the next state based on the
current state and the input symbol.
 Representation: Moore machines are often represented using state transition
diagrams, indicating the outputs associated with each state.
 Complexity: Moore machines are primarily used for modeling systems with
synchronous behaviors.
5. Mealy Machine:
A Mealy machine is a finite state machine in which the outputs are associated with the
transitions.
 Output Function: In a Mealy machine, the output is determined by both the
current state and the input symbol during a transition.
 Transition Function: The transition function specifies the next state based on the
current state and the input symbol.
 Representation: Mealy machines are represented using state transition diagrams,
indicating the outputs associated with each transition.
 Complexity: Mealy machines are commonly used for modeling systems with
combinational behaviors.
Overall, NFA and DFA are used for recognizing regular languages, PDAs for context-free
languages, and Moore/Mealy machines for modeling systems with different types of behaviors.
Each type of machine has its specific characteristics and use cases, catering to different
requirements in the theory of automata.
Summary:
NFA and DFA are both finite state machines used for recognizing regular languages, with NFA
being non-deterministic and allowing multiple possible next states, while DFA is deterministic
and has a unique next state for every input symbol and current state. PDAs, on the other hand,
are more powerful and can recognize context-free languages, thanks to the added stack memory.
Moore machines are deterministic and have outputs associated with states, making them suitable
for modeling systems with synchronous behaviors. Mealy machines, also deterministic, have
outputs associated with transitions and are ideal for modeling systems with combinational
behaviors. Each machine type has its own characteristics and expressive power, catering to
different requirements in automata theory and system modeling.

Toa Ass3 Final

Uploaded by

Copyright:

Available Formats

Toa Ass3 Final

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Toa Ass3 Final

Uploaded by

Copyright:

Available Formats

Kinnaird College for Women, Lahore

Post-Mid Assignment No. 3

Q2. Provide a detailed comparison of different types of machine in theory of

You might also like