Chapter 2_Context-Free Grammar (CFG), Formal Languages, Alphabets, String & Notation

Alphabet

It is defined as a finite set of symbols. We define an ___________ to be any nonempty finite set. The members of the _________ are the symbols of the ___________.

Alphabet

It is denoted by a sigma symbol

string

A “_________” over an alphabet is a finite sequence of symbols from that alphabet, which is usually written next to one another and not separated by commas.

length

The “________” of a string is its ________ as a sequence. The __________ of a string w is written as |w|.

Epsilon E or ε

Lambda Λ or λ

Symbol for null string (2)

pipe symbol | |

length is denoted by?

palindrome

String that is equivalent in its reverse called ____________

Reverse String

It explains the concept of reversing a string mathematically

substring

A string z is a __________ of w if z appears consecutively within w.

concatenation

Assume a string x of length m and string y of length n, the ______________ of x and y is written xy

It is the process of joining two strings together

suffix

If w = xv for some x, then v is a ______ of w.

prefix

If w = vy for some y, then v is a ______ of w.

Context-Free-Grammar

A more powerful method of describing languages.

Context-Free-Grammar

First used in the study of human languages.

specification, compilation

Application of context-free grammars occurs in the ___________ and ___________ of programming languages.

Parser

a component that most compilers and interpreters have. extracts the meaning of a program before generating the compiled code

4

Context-Free-Grammar is defined by __ tuples

finite set of variables or finite set of Non-terminal Symbols

Context-Free-Grammar

V is a?

finite set of terminals

Context-Free-Grammar

∑ or T is a?

start variables

Context-Free-Grammar

S is a?

finite set of production rules

Context-Free-Grammar

P is a?

can be rewritten as, produces

The symbol "⟶" is read

"_____________.“ or

can also be read as “__________.”

production rules

The difference between regular grammar and context-free grammar is the _______________

productions, variable

A grammar consists of a collection of substitution rules, also called ____________. Each rule appears as a line in the grammar, comprising a symbol and a string separated by an arrow. The symbol is called a ___________.

terminals,

capital letters,

lowercase letters,

start variable

The string consists of variables and other symbols called __________. The variable symbols often are represented by ____________.

The terminals are analogous to the input alphabet and often are represented by _____________, numbers, or special symbols.

One variable is designated as the ___________. It usually occurs on the left-hand side of the topmost rule.