Languages, grammar and automata Flashcards
What is the definition of a vocabulary / alphabet?
A vocabulary (or alphabet) V is a finite, nonempty set of elements called symbols. A word (or sentence) over V is a string of finite length of elements of V. The empty string or null string, denoted by λ, is the string containing no symbols. The set of all words over V is denoted by V *. Note that λ is the string containing no symbols. It is different from φ, the empty set. It follows that
{λ} is the set containing exactly one string, namely, the empty string.What is a grammar?
A grammar provides a set of symbols of various types and a set of rules for producing words: A grammar has a vocabulary V , which is a set of symbols used to derive members of the language. Some of the elements of the vocabulary cannot be replaced further by other symbols; these elements are called terminals.
What is a nonterminal?
Members of the vocabulary, which can be replaced further by other symbols (terminals or nonterminals), are called nonterminals.
Can terminal in a grammar be replaced?
No. Some of the elements of the vocabulary cannot be replaced further by other symbols; these elements are called terminals.
What is the start symbol?
There is a special member of the vocabulary called the start symbol, denoted by S, which is the element of the vocabulary that we always begin with our replacements.
What are production rules?
The rules that specify when we can replace a string from V ∗ (the set of all strings of elements in the vocabulary) with another string are called the productions of the grammar. We denote by z0 → z1 the production that specifies that z0 can be replaced by z1 within a string.
Let G be the grammar with vocabulary V = {S, A, a, b}, set of terminals T = {a, b}, starting symbol S, and productions P = {S → aA,S → b,A → aa}. What is the language of the grammar L(G)?
From the start state S we can derive aA using the production S → aA. We can also use the production S → b to derive b. From aA the production A → aa can be used to derive aaa. No additional words can be derived. Hence, L(G) = {b, aaa}.
Let G be the grammar with vocabulary V = {S,0,1}, set of terminals T = {0,1}, starting symbol S, and productions P = {S → 11S,S → 0}. What is L(G), the language of this grammar?
From S we can derive 0 using S → 0, or 11S using S → 11S. From 11S we can derive either 110 or 1111S. From 1111S we can derive 11110 and 111111S. At any stage of a derivation we can either add 11 at the end of the string followed by S or terminate the derivation by adding a final 0. We note that L(G) = {0, 110, 11110, 1111110, . . . }, the set of all strings that begin with an even number of 1 and end with a 0.
Provide a phrase-structure grammar that generates the set {0n 1n |n = 0, 1, 2, . . . }.
Two productions can be used to generate all strings consisting of a string of 0 followed by a string of the same number of 1, including the null string. The first production builds up successively longer strings in the language by adding a 0 at the start of the string and a 1 at its end. The second production replaces S with the empty string. The solution is the grammar G = (V,T,S,P), where V = {0, 1, S}, T = {0, 1}, S is the starting symbol, and the productions are
S → 0S1
S→λ
How can you represent a derivation in the language?
A derivation in the language generated by a context-free grammar can be represented graphically using an ordered rooted tree, called a derivation or parse tree. The root of this tree represents the starting symbol. The internal vertices of the tree represent the nonterminal symbols that arise in the derivation. The leaves of the tree represent the terminal symbols that arise. If the production A → w arises 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.
What is a finite-state machine?
A finite-state machine M = (S, I, O, f, g, s0) consists of a finite set S of states, a finite input alphabet I, a finite output alphabet O, a transition function f that assigns to each pair of state and input a new state, an output function g that assigns to each pair of state and input a corresponding output, and an initial state s0.
How can you use a state table?
We can use a state table to represent the values of the transition function f and the output function g for all pairs of states and input.
How can you use a state diagram?
Another way to represent a finite-state machine is to use a state diagram, which is a directed graph with labeled edges. In this diagram, each state is represented by a circle. Arrows labeled with the input and output pair are shown for each transition.
