TALF units 4-5

Given G=({a,b,c}, {S, B, C}, S, P={S::=aB | bC | a; B::=a | BC | c; C::= c}) Indicate which of the following grammars corresponds to a Chomsky Normal Form grammar equivalent to the previous one:
a. G'=({a,b,c},{S,A,B,C}, S, P'={S::=a | AC; B::=a | c; A::=b} ).
b. G'=({a,b,c},{S,B,C}, S, P'={S::=aB | bC; B::=a | BC | l; C::=c} ).
c. G'=({a,b,c},{S,A,B,C,D}, S, P'={S::=AB | DC | a; A::=a; B::= BC | a | c; C::=c; D::=b }).
d. G'=({a,b,c},{S,B,C}, S, P'={S::=aB | bC | a; A::=a; B::=a | aC | cC ; C::=c }).

c

Given G=({0,1,2,3},{S,A,B,C},S,P),P={S::=A1;A::=0|B2;B ::=A2|3|C3}select the correct answer:
a. The rule B::=A2 is a superfluous rule.
b. It is a recursive grammar.
c. The language described by G is finite.
d. C is an inaccessible symbol.

b

Given G=({a,b},{A,B},A,P={A::=bA|bB|b|a|l;B::=a}), indicate which of the following grammars corresponds to an equivalent grammar without induced axiom:
a. G' =( {a, b}, {A, B, X}, A, P'={A::=bX | bB| b | a | l; X::=bX|bB|b|a; B::=a })
b. G' =( {a, b}, {A, B, X}, A, P'={A::=bX | bB| b | a | l; X::=bA|bB|b|a; B::=a })
c. G’=({a,b},{A},A,P’={A::=bA|ba|b|a|l})
d. G’=({a,b},{A,B},A,P’={A::=bA|b|bB|b|a;B::=a})

a

Given G=({0,1,2}, {S, B, C,D}, S, P={S::=0B|1C|0; B::=2|CB1|0; C::=2; D::=1}) indicate which of the following grammars corresponds to a Greibach Normal Form grammar equivalent to the previous one:
a. G'=({0,1,2},{S,A,B,C,D,E},S,P'={S::=AB|DC|0;A::=0;B: :=CE|0|2;C::=2;
D ::= 1; E ::= DB }).
b. G'=({0,1,2},{S,B},S,P'={S::=0B|12|0;B::=2|2B1|0}).
c. G'=({0,1,2},{S,B,C,D},S,P'={S::=EB|DC|0;B::=2|CBD|0;C: :=2;D::=1;E::=0}).
d. G'=({0,1,2},{S,B,C,D},S,P'={S::=0B|1C|0;B::=2|2BD|0;C: :=2;D::=1}).

d

Given G=({a, b}, {S, A, B, C, D}, S, P) with P={ S::= a|bA; A::= baB|bC; B ::= b|l; C::=abC; D::= ab}), indicate which of the following statements is false:
a. G has no renaming rules.
b. D is a nongenerative symbol.
c. A::=bC is a superfluous rule.
d. B::=l is a non-generative rule.

b

Given the G3LI=({a,b},{S,A,B}, S,P={S::=Bb | Aa | a; A::=b | Sa; B::=Sb | a) Indicate which of the following grammars corresponds to an equivalent G3LI:
a. G'=({a,b}, {S,A,B}, S, P'={S::=a | bB | aA; A::=B | aS; B::=bS | a } )
b. G'=({a,b}, {S,A,B,X}, S, P'={S::=a | bA | aB | aX; A::=aX | a; B::= bX | b; X::=bB | aA })
c. G'=({a,b}, {S,A,B,X}, S, P'={S::=bA | aB | bX | b; A::=a | aX; B::= bX | b; X::=aA | bB })
d. G’=({a,b}, {S,A,B}, S, P’={S::=a | bA | aB; A::= b; B::= b })

b

Given G=({0,1},{A,B,C},A,P={A::=0B;B::=1C|1,C::=0B|1)}, indicate which of them
following AF corresponds to the automaton that accepts the language generated by G:
a. AF=[{0,1 }, {A, B, C, F}, f, A, {F}]
f(A, 0)=B, f(A, λ)=F, f(B, 1)=C, f(B, l)=F, f(B, 1)=B, f(C, 0 )=B, f(C, l)=F, F(C, 1)=C
b. AF=[{0, 1}, {A, B, C, F}, f, A, {F}]
f(A, 0)=B, f(A, λ)=F, f(B, 1)=C, f(B, l)=F, f(B, 1)=F, f(C, 0 )=B, f(C, l)=F, F(C,1 )=F
c. AF=[{0, 1}, {A, B, C, F}, f, A, {F}]
f(A, 0)=B, f(B, 1)=C, f(B, 1)=F, f(C, 0)=B, F(C, 1)=F
d. AF=[{0, 1}, {A, B, C, F}, f, A, {F}]
f(B, 0)=A, f(C, 1)=B, f(B, l)=F, f(B, 0)=C, F(C, l)=F

c

Given G=(Σt ={0,2},Σn ={B,C,S},S,P={S::=0B|0;B::=0C;C::=2|2B }) select the correct answer:
a. 02 is a statement of the language described by G.
b. 002 is the shortest word in the language described by G.
c. 00202 is a word of the language described by G.
d. 0020B is a sentential form of G.

c

Given the following statements, mark the correct option:
a. Compression rules can only be part of Type-0 grammars.
b. Productions of the type A::=aA, where a in ΣT and A in ΣN are only part of the grammars
Type-3.
c. Type-3 grammars cannot contain the axiom on the right hand side of the rules of
production.
d. Productions of the type S ::= λ where S is the axiom are called non-generative rules.

a

Given the following rules of A, A ::= Aa | aba | b, the result of applying the left recursion elimination algorithm is:
a. A::=a|ba|aX|baX;X::=b|bX
b. A::=a|ba|aA|baA;X::=b|bA
c. A::=b|bX;X::=a|ba|aA|baA
d. A::=b|bX;X::=a|ba|aX|baX

d

Given G3LD=({a,b},{S,A,B}, S,P={S::=b|bB|aA; A::=aS|a; B::=bS|b} ) indicate which of the following grammars corresponds to an equivalent G3LI:
a. G'=({a,b},{S,A,B,X}, S, P'={S::=Bb | Aa | Xb | b; A::=a | Xa; B::= Xb | b; X::=Aa | Bb })
b. G'=({a,b},{S,A,B,X}, S, P'={S::=Ab | Ba | Xb | b; A::=a | Xa; B::= Xb | b; X::=Aa | Bb })
c. G'=({a,b},{S,A,B}, S, P'={S::=b | Bb | Aa; A::=a | Sa; B::=Sb | b } )
d. G'=({a,b},{S,A,B,X}, S, P'={S::=b | Bb | Aa; A::=a | Xa; B::=Xb | b; X::=Aa | Bb })

a

Given G=({a, b, c}, {S, B, C, D}, S, P={S :: =aBC | a; B ::= aD| Cb; C ::= c; D ::= b}) indicate which of the following grammars corresponds to a Chomsky Normal Form grammar equivalent to the previous one:
a. G'=({a,b,c},{S,A,B,C,D,E},S,P'={S::=AE|a;A::=a;B::= AD|CD;C::=c;D::=b;E::=BC}).
b. G'=({a, b, c}, {S, B, C, D}, S, P'={S :: =aBC | a; B ::= cBC | aD| cD; C ::= c;D ::= b}
c. G'=({a, b, c}, {S, A, B, C, D, E}, S, P'={S ::= ABC | a; A ::= a; B ::= CBC | AD | CD; C :: =c; D ::= b }).
d. G'=({a, b, c}, {S, B, C, D}, S, P'={ S :: =SE | a; B ::= CE | SD| CD; C ::= c; D ::= b; E::=BC }).

a

Given G=({a,b}, {S, A,B, N}, S, P={S::=a|NN|BA; N::=aB; A::=a; B::=b }) indicate which of the following grammars corresponds to a Greibach Normal Form grammar equivalent to the previous one:
a. G'=({a,b}, {S, A,B, N}, S, P'={S::=a|aBN|bA; N::=aB; A::=a; B: :=b }).
b. G'=({a,b}, {S, A,B }, S, P'={S::=a|abab|ba; A::=a; B::=b }).
c. G'=({a,b}, {S, A,B, N}, S, P'={S::=a|NN|BA; N::=AB; A::=a; B: :=b }).
d. G'=({a,b}, {S, A,B}, S, P'={S::=a|aBaB|ba; A::=a; B::=b }).

a

Given G={ΣT, ΣN, S, P}, indicate which of the following statements is true:
a. If ∀ r inP it is satisfied that the left part is formed by a single symbol NT, then
can ensure that G is a Context Free Grammar.
b. If ∀ r in P it is satisfied that the left part is formed by a single symbol NT, then
can ensure that G is a Regular Grammar.
c. If G has compression rules, then it can be assured that it is a grammar
Context Sensitive.
d. If G is an unrestricted grammar, L(G) can be described by another equivalent G' with sentence structure.

d

Indicate which of the following statements related to the concept of Ambiguity is false:
a. The ambiguity property is undecidable.
b. If a grammar is ambiguous, then the language it describes is ambiguous.
c. A statement is ambiguous if it can be obtained by means of two or more derivation trees.
different.
d. A grammar is ambiguous if it generates at least one ambiguous statement.

b

Given G=({a, b}, {S, A, B, C, D}, S, P) with P={ S::= a|bA; A::= baB|bC; B ::= b|λ; C::=abC; D::= ab}), indicate which of the following statements is false:
a. D is a nongenerative symbol.
b. A::=bC is a superfluous rule.
c. B::=λ is a non-generative rule.
d. G has no renaming rules.

a

Given the following rules of A, A ::= Aa | aba | b, the result of applying the left recursion elimination algorithm is:
a. A::=b|bX;X::=a|ba|aX|baX
b. A::=a | ba | aX | baX; X ::= b | b X
c. A ::= a | ba | aA | baA ; X ::= b | bA
d. A ::= b | bX; X::=a | ba | aA | baA

a

Given AF=[{0,1}, {A,B,C,F}, f, A, {F}] f(A,0)=B, f(A, λ)=F, f(C ,0)=B, f(B,1)=C, f(B,1)=F, indicate which of the following grammars corresponds to the equivalent G3LD:
a. G=({0,1},{A,B,C},A,P={A::=0B|λ,B::=1C|1,C::=0B)}
b. G =( {0, 1}, {A, B, C}, A, P ={B ::= 0A | 1 | 0C; A ::= λ, C ::= 1B )}
c. G =( {0, 1}, {A, B, C}, A, P ={B ::= A0 | C0; F ::= A; C ::= B1 ; F ::= B1)}
d. G =( {0, 1}, {A, B, C}, A, P ={A ::= B0 | λ, B ::= C1 |1 , C ::= B0)}

a

Given G=({a,b},{A,B},A,P={A::=bA|bB|b|a|λ;B::=a}), indicate which of the following grammars corresponds to an equivalent grammar without induced axiom:
a. G' =( {a, b}, {A, B, X}, A, P'={A::=bX | bB| b | a | λ; X::=bX|bB|b|a; B::=a })
b. G' =( {a, b}, {A, B, X}, A, P'={A::=bX | bB| b | a | λ; X::=bA|bB|b|a; B::=a })
c. G’ =( {a, b}, {A}, A, P’={A::=bA | ba| b | a |λ})
d. G’ =( {a, b}, {A, B}, A, P’={A::=bA | b | bB| b | a; B::=a })

a

Given G=(Σt ={a,c}, Σn ={B,C,S},S,P={S::=aB|a;B::=aC;C::=c|cB }) select the correct answer:
a. ac is a statement of the language described by G.
b. aac is the shortest word in the language described by G.
c. aacaB is a sentential form of G.
d. aacac is a word from the language described by G.

d

TRUE OR FALSE:
The set of rules A::=BC, B::=λ, C::= λ, where A,B,C Є ΣN and Axiom=A, can be transformed into the equivalent set A::=B, A:: =C, A::=BC

false

TRUE OR FALSE:
The grammar whose production rules are P={A::=BC |B|a, B::=b|A , C::=c} is ambiguous.

true

TRUE OR FALSE: A::=A is a renaming rule.

false

TRUE OR FALSE: Two grammars are equivalent if they generate the same language.

true

TRUE OR FALSE:
A::=aBC is a rule in FNG.

true

TRUE OR FALSE: Any language generated by a G3 can be generated by an equivalent G2.

true

TRUE OR FALSE: A::= λ is a Nongenerative rule if and only if A is not the axiom of the grammar.

true

TRUE OR FALSE: Every Type 1 Grammar is also a Type 2 Grammar.

false

TRUE OR FALSE: If we want to remove the left recursion from the following grammar:
G = ({a,b},{S},S,P) where P={S::=aSb | SS | λ}, we can obtain the following equivalent grammar: G = ({a,b},{S,X},S,P) where P={S::=aSb | aSbX | λ, X::=SX | yes }

true

TRUE OR FALSE: Only type 2 grammars are ambiguous

false

TRUE OR FALSE: The production rule Ca::=aaC, where a Є ΣT and C Є ΣN, belongs to a type 2 grammar in the Chomsky hierarchy.

false

TRUE OR FALSE: S::= λ is a rule in FNC

true

TRUE OR FALSE: If the axiom is replaced by a nongenerative symbol, the language generated by the grammar is the empty language.

true

TRUE OR FALSE: The terminal and nonterminal alphabets of a grammar are disjoint.

true

TRUE OR FALSE: In a sentential form only non-terminal symbols can appear.

false

TRUE OR FALSE: S-->A-->B is a lead of length 3

false

TRUE OR FALSE: If a statement can be obtained in a G by means of 2 or more different derivation trees, the statement is ambiguous.

true

TRUE OR FALSE: It is possible that a Grammar has superfluous rules that contribute to the formation of words.

false

TRUE OR FALSE: If no unambiguous grammar can be found to generate a given language, then we say that the language is inherently ambiguous. FALSE:

true

TRUE OR FALSE: Given the grammar:
G=(ΣT , ΣN , S, P), such that ΣT = {1,0} ΣN = {S,B},
P={ S::=1B, S::=1, B::=0S},
can be transformed into the equivalent grammar
G1 =(ΣT , ΣN , S, P1), such that ΣT = {1,0} ΣN = {S,B,C}, P1={S::=1B, S::=1, B::= 0C, C::=1B, C::=1}

True

Check the true statements:
a. ABC::=AB is a rule of a type 1 context-sensitive grammar.
b. Every regular grammar is also an independent grammar.
of the context.
c. Every type 0 grammar can be transformed into a sensible grammar.
to the equivalent context.
d. Any type 0 grammar with no sentence structure
can be able
be transformed into an equivalent grammar of type 0 with structure
of phrase.

b,c

Mark the true statements
:a. If α is a regular expression, then αα∗ =α∗
b. If α is a regular expression, then αα∗ =α∗α
c. Db (a*(a+b)*) = (a+b)*
d.δ (a*bb ) =λ

b,c

Check the true statements:
a. The language L={a^(n+2)b^(n)} can be recognized by an AP.
b. A language that has λ as one of its words can be accepted by some AP.
c. If in an AP Γ={Α}, Q={p,q}, where p is the initial state, then the corresponding grammar will have among its rules S::=(p, A, p) | (p,A,q)
d. f(p, x, R) = (p, R) corresponds to the movement (p, xB, RP) |- (p,B, RP)

a,b,c,d