Matematika Diskrit : Relasi, Sifat Relasi, dan Contoh Soal

Struktur Diskrit : Dasar-Dasar Bahasa Formal, Grammar, dan Language

Modelling Computation

Models of computation help us to answer the following questions:

• Can a task be carried out using computer ? 
• If YES, How can the task be carried out ?

Three types of structures used in models computation:

• Grammars Used to generate words of a language and determine whether a word is in a language:
• Finite-state machines Used in modeling a problem.
• Turing machines Used to classify problems as tractable/intractable and solvable/unsolvable

Languages and Grammars

Natural languages and formal languages

Natural Language is spoken language. It is not possible to specify all the rules of syntax (form) in Natural language. One of the rules is English grammars. 

Formal Language which are generated by grammars, provide models for both natural languages and programming languages. Formal Language specified by a well defined set of rules/syntax.

Grammars help us answer the following questions:

• How can we determine whether a combination of words is a valid sentence in a formal language ?
• How can we generate the valid sentences of a formal language ?

Generating a Subset of English

Rules :

• a sentence is made up of a noun phrase followed by a verb phrase;
• a noun phrase is made up of an article followed by an adjective followed by a noun,
• a noun phrase is made up of an article followed by a noun;
• a verb phrase is made up of a verb followed by an adverb, or
• a verb phrase is made up of a verb;
• an article is a, or
• an article is the;
• an adjective is large, or
• an adjective is hungry;
• a noun is rabbit, or
• a noun is mathematician;
• a verb is eats, or
• a verb is hops;
• an adverb is quickly, or
• an adverb is wildly.

Basic Terminologies

A vocabulary/alphabet, V is a finite nonempty set of elements called symbols. Example: V = {a, b, c, A, B, C, S}

A word/sentence over V is a string of finite length of elements of V. Example: Aba

The empty/null string, λ is the string with no symbols. 

V* is the set of all words over V. Example: V* = {Aba, BBa, bAA, cab …} 

A language over V is a subset of V*.

• We can give some criteria to a word to be in a language.
• Example: cab is a subset in V* and is a language.

Phrase-Structure Grammars

A Phrase-Structure Grammars G = (V, T, S, P) consists of:

• a vocabulary V,
• a subset T of V consisting of terminal elements
• a start symbol S from V
• a finite set of productions P 

Elements of N = V – T are called nonterminal symbols. Every production in P must contain at least one nonterminal on its left side.

EXAMPLE 1: 

qLet G = (V, T, S, P), where V = {a, b, A, B, S}, T = {a, b}, S is a start symbol and P = {S → ABa, A → BB, B → ab, A → Bb}. Then, G is a Phrase-Structure Grammar.

Language L(G) of a Grammar G

Suppose w and w’ are words over the vocabulary set V of a grammar G. Then:

• We write w ⇒ w’ if w’ can be obtained from w by using one of the productions (w’ is directly derivable from w)
• We write w ⇒ w’ if w’ can be obtained from w by using a finite number of productions (w’ is derivable from w)

The language of G consists of all words in terminal set T that can be obtained from the start symbol S by the above process: 

L (G) = { w Є T*: S ⇒ w} 

EXAMPLE: 

Let G = (V, T, S, P), where V = {a, b, A, S}, T = {a, b}, S is a start symbol and P = {S → aA, S → b, A → aa}. The language of this grammar is given by L (G) = {b, aaa}; since we can derive aA from using S → aA, and then derive aaa using A → aa. We can also derive b using S → b.

Examples 2 - 3

Examples 4

Examples 5

Examples 6

Examples 7

Types of Grammar

Derivation Tree of Context-Free Grammar

Represents the language using an ordered rooted tree.

Root represents the starting symbol. Internal vertices represent the nonterminal symbol that arise in the production. Leaves represent the terminal symbols. 

If the production A → w arise in the derivation, where w is a word, the vertex that represents A has as children vertices that represent each symbol in w, in order from left to right.

Example: Derivation Tree

Let G be a context-free grammar with the productions 

P = {S →aAB, A →Bba, B →bB, B →c}.

The word w = acbabc can be derived from S as follows:

S ⇒ aAB →a(Bba)B ⇒ acbaB ⇒ acba(bB) ⇒ acbabc

Thus, the derivation tree is given as follows:

Exercises

Construct phrase-structure grammars to generate each of these sets.

• {1n | n ≥ 0}
• {10n | n ≥ 0}
• {(11) n | n ≥ 0} 

Let G be the grammar with V = {a, b, c, S}; T = {a, b, c}; starting symbol S; and productions S → abS, S → bcS, S → bbS, S → a, and S → cb. Construct derivation trees for

• bcbba.
• bbbcbba
• bcabbbbbcb

Sumber

Slide Strukdis : Dasar Bahasa Formal