- Член од
- 8 септември 2010
- Мислења
- 13
- Поени од реакции
- 0
Имам неколку задачи кои морам да ги решам... но некако не ми оди! Ќе може ли некој да ми помогне? Ќе му бидам многу благодарен. 
Меѓудругото задачите се на англиски, па ако може некој да ги реши многу ќе ми помогни
)
Еве ги задачите :
Proposed Exercise 2.1.Consider the grammar G = { NT = {A,B,C}, A = {a, b, c}, П = {A ::= aA | b; B ::= ACb | ACB; C ::= ca}, A}, (where A is the starting symbol, and L(G) denotes the language obtained by G). Check if the string abbcab Є L(G) and if the string daccca Є L(G). Then, discuss if it is possible to prove that L(G) produces only strings of length less than 12 elements or not, and, finally, discuss if it is possible to prove that L(G) is infinite.
Proposed Exercise 2.2.Consider the grammar G = {NT = {A,B,C}, A = {a, b, c}, П = {A ::= aA | B | a; B ::= ACb | ACA | bb; C ::= ca | b}, A}, (where A is the starting symbol, and L(G) denotes the language obtained by G). Check if the strings band abbcaba re ambiguous. Discuss if it is possible to prove there is only one ambiguous string in L(G), and, finally, check if the string ba is ambiguous.
Proposed Exercise 2.3.Consider the strings 110 and 0011, and the grammar G = {NT = {A,B,C}, A = {0,1}, П = {A ::= 1B | 00B; B ::= 1 | 1B |C;C ::= 10B;} ,A}, (where A is the starting symbol, and L(G) denotes the
language obtained by G). Check if the strings 110 and 0011 belong to L(G).
Check if the language L(G) contains at least one string composed by exactly one terminal symbol. Does any of the strings of the type 110n0 belong to L(G)?
Proposed Exercise 2.4.Consider set of terminal symbols A = {a, b, c}, and the string aabcc. Check if it does belong to L(G), where G = {NT = {A,B,C}, П = {A ::= b | BAC; B ::= a | aB; C ::= c | Cc | cc}; A}. Then, check if it does belong to L(G’), where G’= {NT = {A,B,C}; П = {A ::= bc | BAC; B ::= a | aB; C ::= Cc | cc}; A}. Check if it does belong to L(G’’),
where G’’= {NT = {A,B,C}; П = {A ::= bc | BAC | c; B ::= a | aB; C ::= A | cc}; A}. Finally, check if the given string is ambiguous in the grammar G(assuming that it is derivable in it).
Proposed Exercise 2.5.Consider the grammar G = {NT = {S}; A = {a; b; c}; П = {S ::= c | aSa | bSb}; S}, (where S is the starting symbol, and L(G) denotes the language obtained by G) and check if: the string aacaaa Є L(G); if the string aaacbb Є L(G); if the string ababcbaba Є L(G). Then, check if the language L(G) is formed by all and only palindrome (=that can be read from left to right and vice-versa) strings obtained by using a; b and having a c right in the middle.
Proposed Exercise 2.6.Consider the grammar G = {NT = {S,T}; A = {a; b; c}; П = {S ::= c | T | aTa | bSb; T ::= c | S | aSa | bT b}; S}, (where S is the starting symbol, and L(G) denotes the language obtained by G) and check
if: the string aacaaa Є L(G); the string aaacbb Є L(G); the string, abcba, which is in L(G), is ambiguous. Then, check if the language L(G) is formed by all and only palindrome (=that can be read from left to right and vice-versa) strings obtained by using a, b and having a c right in the middle.
Proposed Exercise 2.7.Consider the grammar G = {NT = {S,A}; A = {a};П = {S ::= AA;A ::= AAA | a}, S}, (where S is the starting symbol, and L(G) denotes the language obtained by G) and check if: the string aaaaa Є L(G); the string aaaa Є L(G); the string aaaa is ambiguous. Finally, discuss
if the language L(G) is formed by all and only strings formed by aof a even (nonzero) length.
Меѓудругото задачите се на англиски, па ако може некој да ги реши многу ќе ми помогни
) Еве ги задачите :
Proposed Exercise 2.1.Consider the grammar G = { NT = {A,B,C}, A = {a, b, c}, П = {A ::= aA | b; B ::= ACb | ACB; C ::= ca}, A}, (where A is the starting symbol, and L(G) denotes the language obtained by G). Check if the string abbcab Є L(G) and if the string daccca Є L(G). Then, discuss if it is possible to prove that L(G) produces only strings of length less than 12 elements or not, and, finally, discuss if it is possible to prove that L(G) is infinite.
Proposed Exercise 2.2.Consider the grammar G = {NT = {A,B,C}, A = {a, b, c}, П = {A ::= aA | B | a; B ::= ACb | ACA | bb; C ::= ca | b}, A}, (where A is the starting symbol, and L(G) denotes the language obtained by G). Check if the strings band abbcaba re ambiguous. Discuss if it is possible to prove there is only one ambiguous string in L(G), and, finally, check if the string ba is ambiguous.
Proposed Exercise 2.3.Consider the strings 110 and 0011, and the grammar G = {NT = {A,B,C}, A = {0,1}, П = {A ::= 1B | 00B; B ::= 1 | 1B |C;C ::= 10B;} ,A}, (where A is the starting symbol, and L(G) denotes the
language obtained by G). Check if the strings 110 and 0011 belong to L(G).
Check if the language L(G) contains at least one string composed by exactly one terminal symbol. Does any of the strings of the type 110n0 belong to L(G)?
Proposed Exercise 2.4.Consider set of terminal symbols A = {a, b, c}, and the string aabcc. Check if it does belong to L(G), where G = {NT = {A,B,C}, П = {A ::= b | BAC; B ::= a | aB; C ::= c | Cc | cc}; A}. Then, check if it does belong to L(G’), where G’= {NT = {A,B,C}; П = {A ::= bc | BAC; B ::= a | aB; C ::= Cc | cc}; A}. Check if it does belong to L(G’’),
where G’’= {NT = {A,B,C}; П = {A ::= bc | BAC | c; B ::= a | aB; C ::= A | cc}; A}. Finally, check if the given string is ambiguous in the grammar G(assuming that it is derivable in it).
Proposed Exercise 2.5.Consider the grammar G = {NT = {S}; A = {a; b; c}; П = {S ::= c | aSa | bSb}; S}, (where S is the starting symbol, and L(G) denotes the language obtained by G) and check if: the string aacaaa Є L(G); if the string aaacbb Є L(G); if the string ababcbaba Є L(G). Then, check if the language L(G) is formed by all and only palindrome (=that can be read from left to right and vice-versa) strings obtained by using a; b and having a c right in the middle.
Proposed Exercise 2.6.Consider the grammar G = {NT = {S,T}; A = {a; b; c}; П = {S ::= c | T | aTa | bSb; T ::= c | S | aSa | bT b}; S}, (where S is the starting symbol, and L(G) denotes the language obtained by G) and check
if: the string aacaaa Є L(G); the string aaacbb Є L(G); the string, abcba, which is in L(G), is ambiguous. Then, check if the language L(G) is formed by all and only palindrome (=that can be read from left to right and vice-versa) strings obtained by using a, b and having a c right in the middle.
Proposed Exercise 2.7.Consider the grammar G = {NT = {S,A}; A = {a};П = {S ::= AA;A ::= AAA | a}, S}, (where S is the starting symbol, and L(G) denotes the language obtained by G) and check if: the string aaaaa Є L(G); the string aaaa Є L(G); the string aaaa is ambiguous. Finally, discuss
if the language L(G) is formed by all and only strings formed by aof a even (nonzero) length.
