Automata

Question 1

Formal language

Answer 1

i. Strict rules govern the structure and arrangement of symbols and words in formal languages
ii. Every expression OR statement in a formal language has a clear and unambiguous meaning
iii. Formal languages often have a set of rules and grammar that define the valid combinations of symbols and how they can be manipulated

Question 2

De-morgan’s Law

Answer 2

De-morgan’s Law is a pair of fundamental rules in boolean algebras. These laws describe the relationships between logical AND, OR, and NOT operations.

Question 3

First Law (De Morgan’s Theorem for AND ):

Answer 3

i. The negation of conjunction (AND) is equivalent to the disjunction (OR) of the negations of the individual statement.
¬(A∧B)=(¬A)∨(¬B)

Question 4

Second Law (De Morgan’s Theorem for OR)

Answer 4

i. The negation of a disjunction (OR) is equivalent to the conjunction (AND) of the negations of the individual statements
ii. ¬(A∨B)=(¬A)∧(¬B)

Question 5

Grammar

Answer 5

A grammar in automata refers to a set of rules specifying how strings of symbols can be constructed in a formal language

Question 6

Deterministic finite automata

Answer 6

A deterministic finite automaton (DFA) is a finite state machine that recognizes or accepts a set of strings over an alphabet

Question 7

Non-deterministic Finite Automata

Answer 7

A Non-deterministic Finite Automaton (NFA) is a finite state machine that recognizes or accepts a set of strings over an alphabet.

Question 8

Equivalence of NFA and DFAs

Answer 8

Every language that can be recognized by a non-deterministic finite automaton (NFA) can also be recognized by a deterministic finite automaton (DFA), and vice versa.

Question 9

subset construction

Answer 9

Given any NFA, there exists an equivalent DFA that recognizes the same language. This process is known as the subset construction.

Question 10

Concatenation closure

Answer 10

The class of regular languages is closed under the concatenation operation.

Question 11

Kleene’s Star Closure

Answer 11

The class of regular languages is closed under the Kleene star operation.

Question 12

pumping lemma for regular languages

Answer 12

For any regular language L, there exists a constant p (the “pumping length”) such that any string s in L with length at least p can be split into three parts, xyz, satisfying certain conditions. This lemma is used to prove that certain languages are not regular.

Question 13

Regular Expression

Answer 13

i. Basic Symbols
ii. Concatenation ( Concat )
iii. Union
iv. Kleen Star
v. alphabets
vi. parentheses
vii. wildcard (dot)
viii. Character classes
ix. Escape
x. Anchors ( ^ and $)
xi. Quantifiers
xii. Escape Sequence
xiii. Regular Expression

Question 14

properties of regular languages

Answer 14

i. Regular languages satisfy the pumping lemma, which provides a condition for proving that a language is not regular
ii. The membership problem for regular languages (deciding whether a given string is in the language ) is decidable
iiI. Regular Language can be recognized by both deterministic finite automata (DFA) and non-deterministic finite automata (NFA) with equivalent expressive power
iii. Every regular language can represented by a regular expression, demonstrating their expressive power

Question 15

Pigeonhole Principle

Answer 15

The pigeonhole principle states that if you want to distribute n items into m containers and n > m, then at least one container must contain more than one item.

Question 16

nullable in automata

Answer 16

A non-terminal symbol in a grammar is said to be “nullable” and refers to whether a non-terminal symbol in a grammar can derive the empty string (or epsilon )

Question 17

two important normal forms

Answer 17

i. Chomsky normal form
ii. Greibach Normal Form (GNF)
iii. Backus-Naur Form ( BNF)

Question 18

Chomsky Normal Form

Answer 18

In Chomsky’s normal form, every production rule in context-free grammar is of the form A–> BC or A–>a, where A, B, and C are non-terminals, and ‘a’ is a terminal.

Question 19

Greibach Normal Form

Answer 19

In Griebach Normal Form, every production rule in a context-free grammar is of the form A–> a(gamma), where A is a non-terminal, ‘a’ is a terminal, and gamma is a strong of non-terminals.

Question 20

Backus-Naur Form

Answer 20

Backus-Naur Form is not a “normal form” in the traditional sense, but it’s a widely used notation for expressing context-free grammars, often used to define the syntax of programming languages.