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 ## Footnote 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 (∑) ## Footnote **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** ## Footnote ∑* = ∑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 ## Footnote 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

 ## Footnote 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

{ Λ } ## Footnote 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) ## Footnote 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. ## Footnote **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**. ## Footnote See presentation for examples

Answer 57

Noted