MODULES 1-3

Question 1

COURSE: RECAP

Course code

Answer 1

S-CSPC327

Question 2

COURSE: RECAP

Course title

Answer 2

Automata Theory and Formal Languages

Question 3

COURSE: RECAP

Full name of the professor

Answer 3

Ms. Jennylinde R. Manaois

Question 4

COURSE: RECAP

The course allows the students to analyze formal models in computer science, including _, _, _, _, and _.

Answer 4

regular expressions,
finite automata,
context-free grammars,
pushdown automata,
Turing machines

Question 5

COURSE: RECAP

At the end of the course, the students are expected to develop a simple _ that will check the syntax of a certain string if it is a valid string or not in a particular language.

Answer 5

compiler

Question 6

COURSE: RECAP

Module 1: Introduction to Computer Theory
Module 2: Regular Expression
Module 3: Finite Automata

Answer 6

Noted

Question 7

MODULE 1: QUESTION

It is the study of abstract computing devices or “machines.”

Answer 7

Automata Theory

Question 8

MODULE 1: QUESTION

It is a study of mathematical model of a computer which can determine whether a particular string is in a language.

Answer 8

Automata Theory

Question 9

MODULE 1: QUESTION

It is a concept that describes how machine mimic human behavior.

Answer 9

Automata Theory

Question 10

MODULE 1: QUESTION

It is an abstract model of a digital computer.

Answer 10

Automata

Question 11

MODULE 1: INFO

Every automaton includes some essential features.
* It has mechanism for reading input.
* It is also assumed to operate in a discrete time frame.

Answer 11

Noted

Question 12

MODULE 1: QUESTION

Every automaton has a mechanism for reading _.

Answer 12

input

Question 13

MODULE 1: QUESTION

An automaton is assumed to operate in a _ time frame.

Answer 13

discrete

Question 14

MODULE 1: QUESTION

It provides a model way in which computers can parse some language.

Answer 14

Automata

Question 15

MODULE 1: QUESTION

A mathematical model for a finite state machine.

Answer 15

Automata

Question 16

MODULE 1: QUESTION

It is a machine that given an input, jumps through a series of states according to a transition function that tells the automaton which state to go next given a current state and a current symbol.

Answer 16

Finite State Machine

Question 17

MODULE 1: INFO

Brief History of Automata
* Alan Turing in the 1930’s introduced his abstract model – Turing Machines – that had all the capabilities of today’s computers.
* In the 1940’s and 1950’s, simpler kinds of machines, called finite automata were studied by Rabin, Scott and others.
* In the late 1950’s, Noam Chomsky introduced formal grammars representing languages accepted by abstract automata.

Answer 17

Noted

Question 18

MODULE 1: QUESTION

These are the most powerful abstract machines.

Answer 18

Turing Machines

Question 19

MODULE 1: INFO

Why study Automata?

Finite Automata are useful model for many important kinds of hardware and software.

Answer 19

Noted

Question 20

MODULE 1: INFO

List of Some Applications of the Concept of Finite Automata
* Software for designing and checking the behavior of digital circuits. (ex. on/off switch)
* The “lexical analyzer” of a typical compiler.
* Software for scanning large bodies of text, such as collections of Web pages, to find occurrences of words, phrases, or other patterns.
* Software for verifying systems of all types that have a finite number of distinct states.

Answer 20

Noted

Question 21

MODULE 1: INFO

There are important notations that are not automaton-like, but play an important role in the study of automata and their application.
1. Grammars
2. Regular Expression

Answer 21

Noted

Question 22

MODULE 1: RECAP

Automaton-like formal models in Computer Science

Answer 22

Finite Automata, Pushdown Automata, and the Turing machines

Question 23

MODULE 1: RECAP

Non-automaton-like formal models in Computer Science

Answer 23

Grammars and Regular Expression

Question 24

MODULE 1: QUESTION

These are useful models when designing software that processes data with a recursive structure.

Answer 24

Grammars

The best known example is a parser – the component of a compiler that deals with recursively nested features of the typical programming languages.

Question 25

MODULE 1: QUESTION

The component of a compiler that deals with recursively nested features of the typical programming languages.

Answer 25

parser

The best known example of Grammars.

Question 26

MODULE 1: QUESTION

This denotes the structure of data, especially text strings.

Answer 26

Regular Expression

Question 27

MODULE 1: INFO

Introduction to Computer Theory Summary
* Core mathematics of CS (not changed in over 30 years)
* Many applications, especially in design f compilers and programming languages
* To be able to recognize incomputable and intractable problems
* In order to be computer scientist, not simply a computer programmer

Answer 27

Noted

Question 28

MODULE 1: QUESTION

_ is any finite set of symbols.

Answer 28

Alphabet (∑)

Common alphabets include:
1. ∑ = { 0,1 } - binary alphabet
2. ∑ = { a,b, …., z } - the set of all lowercase letters
3. The set of all ASCII characters, or the set of all printable ASCII characters.

Question 29

MODULE 1: RECAP

A symbol that denotes alphabets

Answer 29

∑

Question 30

MODULE 1: QUESTION

_ is a finite sequence of symbols from some alphabet.

Answer 30

String ( Word )

e.g. aba, 01001

Question 31

MODULE 1: QUESTION

The empty string with zero occurrences
of symbols is denoted by _.

Answer 31

Λ

Question 32

MODULE 1: QUESTION

It is the number of positions for symbols in the string.

Answer 32

String length

Question 33

MODULE 1: QUESTION

String length is denoted by _

Answer 33

|string|

e.g. |0110| = 4, |Λ| = 0

Question 34

MODULE 1: INFO

Powers of an alphabet ∑ is defined as the set of strings of length k and denoted by ∑^k.

k - length of string

Answer 34

Noted

Question 35

MODULE 1: QUESTION

The set of all strings over an alphabet ∑ is denoted by _

Answer 35

∑*

Alphabet symbol with Kleene Closure

∑* = ∑0  ∑1  ∑2  ….

Question 36

MODULE 1: QUESTION

The set of nonempty strings over ∑ is denoted by _.

Answer 36

∑+

Alphabet symbol with Positive Closure

Question 37

MODULE 1: INFO

String Concatenation
if x and y are strings then xy denotes the concatenation of x and y.

Answer 37

Noted

Question 38

MODULE 1: QUESTION

It is the set of strings ( words ) chosen from some alphabet

Answer 38

Language

The language may be infinite, but there is some finite set of symbols of which all its strings are composed.

Question 39

MODULE 1: QUESTION

This denotes the empty language over any alphabet.

Answer 39



A symbol resembling a stop sign, but with a longer horizontal line extending from right to left across its center.

Question 40

MODULE 1: QUESTION

It is the symbol of the language consisting of only the empty string.

Answer 40

{ Λ }

An upside down V inside the curly braces.

Question 41

MODULE 1: INFO

Note that { Λ } ≠  (empty language)
The former has one string, the latter has no strings.

Answer 41

Noted

Question 42

MODULE 1: INFO

Some examples of Languages
1. The set of all binary strings consisting of some number of 0’s followed by an equal number of 1’s
2. The language of all strings consisting of n 0’s followed by n 1’s, for some n ≥ 0
3. The set of compilable C programs
4. English words

Answer 42

Noted

Question 43

MODULE 1: INFO

“Set-former” as a Way to Define Languages:
{w|something about w }
1. {w | w consists of an equal number of 0’s and 1’s} (*)
2. {w | w is syntactically correct C program}
3. {w | w is a set of words built according to the rules
of English grammar}
4. {0^n1^n | n ≥ 0}

Answer 43

Noted

Question 44

MODULE 2: QUESTION

It is a sequence of pattern that defines a string.

Answer 44

Regular Expression

Question 45

MODULE 2: QUESTION

These are used to match character combinations in strings.

Answer 45

Regular Expression

Question 46

MODULE 2: QUESTION

String searching algorithm used this pattern to find the operations on a string.

Answer 46

Regular Expression

Question 47

MODULE 2: QUESTION

It is the most effective way to represent any language.

Answer 47

Regular Expression

Question 48

MODULE 2: INFO

The symbols that appear in regular expressions are the letters of the alphabet (Σ), the symbol for the null string (Λ), parentheses (), the star operator (*), and the plus (or) sign (+).

Answer 48

Noted

Question 49

MODULE 2: INFO

The set of regular expressions is defined by the following rules:

Rule 1: Every letter of Σ can be made into a regular expression by writing it in boldface; Λ is a regular expression.

Rule 2: If r1, and r2 are regular expressions, then so are:
1. (rl)
2. r1r2
3. r 1 + r 2
4. rl*

Rule 3: Nothing else is a regular expression.

Answer 49

Noted

Question 50

MODULE 2: INFO

The various operations on regular language are:

Union: If L and M are two regular languages then their union L U M is also a union.
1. L U M = {s | s is in L or s is in M}

Intersection: If L and M are two regular languages then their intersection is also an intersection.
1. L ⋂ M = {st | s is in L and t is in M}

Kleene closure: If L is a regular language then its Kleene closure L1* will also be a regular language.
1. L* = Zero or more occurrence of language L

Answer 50

Noted

Question 51

MODULE 2: INFO

Some RE Examples:

Regular Expression | Regular Set

(0+10*) | L= { 0, 1, 10, 100, 1000, 10000, … }

(0* 1 0*) | L= {1, 01, 10, 010, 0010, …}

(0+ε)(1+ Λ) | L= {Λ0, 1, 01}

(a+b)* | Set of strings of a’s and b’s of any length including the null string. So L= { ε, a, b, aa, ab, bb, ba, aaa, …}

(a+b)*abb | Set of strings of a’s and b’s ending with the string abb. So L = {abb, aabb, babb, aaabb, ababb, …}

(11)* | Set consisting of even number of 1’s including empty string

Answer 51

Noted

Question 52

MODULE 3: QUESTION

It is the simplest abstract machine to recognize patterns with input taken from the given alphabet.

Answer 52

Finite Automata (FA)

The job of an FA is to accept or reject an input depending on whether the pattern defined by the FA occurs in the input.

Question 53

MODULE 3: QUESTION

Its job is to accept or reject an input depending on whether the pattern defined by this occurs in the input.

Answer 53

Finite Automata (FA)

Question 54

MODULE 3: INFO

A finite automaton is a collection of three things:
1. A finite set of states, one of which is designated as the initial state, called the start state, and some of which are designated as final states.
2. An alphabet Σ of possible input letters, from which are formed strings, that are to be read one letter at a time.
3. A finite set of transitions that tell for each state and for each letter of the input alphabet which state to go to next.

Answer 54

Noted

Question 55

MODULE 3: QUESTION

What are the two types of Finite Automaton?

Answer 55

1. Deterministic Finite Automaton (DFA)
2. Non-deterministic Finite Automaton (NDFA/NFA)

Question 56

MODULE 3: INFO

DETERMINISTIC FINITE AUTOMATA

• 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 (Λ) move is not allowed, i.e., DFA cannot change state without any input character.
• For example, below DFA with Σ = {a, b} accepts all strings starting with either a or b.

NOTE:
* There can be many possible DFAs for a pattern.
* A DFA with minimum number of states is generally preferred.

See presentation for examples

Answer 56

Noted

Question 57

MODULE 3: INFO

NON-DETERMINISTIC FINITE AUTOMATA (NFA)

NFA is similar to DFA except following additional features:

1. Null (Λ) 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.

See presentation for examples

Answer 57

Noted