1 حل اسئلة نظرية الاحتساب قسم الحاسوب الجامعة المستنصرية نموذج رقم

Question # 1/ [30 marks] Choose the most suitable answer. Answer 30 ONLY

1. Given the following recursive definition of a set S. What the set S is?

Basis: 1 is in set S

Recursive Step: if x is in set S so is x+x

Closure: only numbers generated from the above two steps are in set S

A. S is a set of positive integers, i.e. {1,2,3,4,5,6,...}

B. S is a set of numbers which are powers of 2, i.e. {1,2,4,8,16,32,...}

C. S is a set of squared numbers, i.e. {1,4,9,16,25,36,...}

D. S is a set of positive even numbers, i.e. {2,4,6,8,10,12,...}

2. Let L = {w ∈ (0 + 1)*|w has even number of 1’s }, i.e. L is the set of all bit strings with even

number of 1’s. Which one of the regular expressions below does not represent L?

A. (0*10*1)* B. 0*(10*10*)* C. 0*(10*1*)*0* D. 0*1(10*1)*10*

3. For which of the following applications are regular expressions used for ?

A. Designing Lexical Analyzer B. Designing Syntax Analyzer

C. Designing Semantic Analyzer D. None of the answers

4. Given the finite state machine M shown aside, L(M) is the set of all strings that __________.

A. begin either with 0 or 1 B. end with 0

C. end with 00 D. contain the substring 00

5. Which one of the following languages over the alphabet {0,1} is described by the regular

expression: (0+1)*0 (0+1)* 0 (0+1)*

A. The set of all strings containing the substring 00

B. The set of all strings containing at most two 0’s.

C. The set of all strings containing at least two 0’s.

D. The set of all strings that begin and end with either 0 or 1.

6. In the Mealy machine of binary incrementer if the input is 1000 , the output will be

A. 0000 B. 1111 C. 1001 D. 1010

7. Moore machine is considered as

A. divider B. half adder C. counter D. invertor

8. Match the following NFAs with the regular expressions they correspond to.

1. ε + 0(01*1 + 00) * 01*

2. ε + 0(10 *1 + 00) * 0

3. ε + 0(10 *1 + 10) *1

4. ε + 0(10 *1 + 10) *10 *

NFA Q: Matches with regular expression 1. ε + 0(01*1 + 00)* 01*
NFA R: Matches with regular expression 2. ε + 0(01*1 + 00)*0
NFA S: Matches with regular expression 3. ε + 0(10*1 + 10)*1
NFA P: Matches with regular expression 4. ε + (010*1 + 10)*10*

A. P -2, Q - 1, R - 3, S - 4 B. P -1, Q - 3, R - 2, S - 4

C. P -1, Q - 2, R - 3, S - 4 D. P - 3, Q - 2, R -1, S - 4

9. Consider the following Finite State Automaton M, which of the regular expressions shown aside

best describes L(M) :

A. b* ab* ab* ab*

B. (a + b) *

C. ( b*a) +

D. b* ab* ab*

10. Given the language L = {ab, aa, baa}. Which of the following strings are in L* ?

1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa

A. 1, 2 and 3 B. 2, 3 and 4 C. 1, 2 and 4 D. 1, 3 and 4

11. Consider the following Finite State Automaton M shown , the complement of L(M) is ____

A. Φ B. { Ԑ }

C. a* D. {a,Ԑ}

12. Consider the languages L1=Φ and L2={a}. Which of the following represents L1*ᴜ L2* ?

A. Φ B. { Ԑ } C. {a*} D. {Ԑ,a*}

13. Let L1 = { ω ∈ {0,1}+| ω has at least as many occurrences of (110)'s }, and let L2 ={ ω ∈{0,1}+

| ω has at least as many occurrences of (000)'s as (111)'s }. Which one of the following is TRUE?

A. L1 is regular but not L2

B. L2 is regular but not L1

C. Both L1 and L2 are regular

D. Neither L1 nor L2 are regular

14. Which of the regular expressions given below represent the following DFA?

I. 0*1(1+00*1)*

II. (0*11* ) + (11* 0+ 1)

III. (0+1)*1

A. I and II only B. I and III only C. II and IIl only D. I , II , and III

15. Consider the NFA shown below, What is the result of the following: δ*(q0, 0011)

A. {q0, q1 } B. {q0, q1,q2}

C. {q0, q1, q2,q3} D. { q3}

16. The minimum number of states in a DFA that accepts the language defined by the regular

expression : (0+1)* (0+1) (0+1)* is __________.

A. 3 B. 4 C. 2 D. 1

17. Consider the language L given by the regular expression (a+b)* b (a+b) over the alphabet {a,b}.The smallest number of states needed in a DFA accepting L is __________.

A. 3 B. 4 C. 5 D. 2

18. Given the transition table below of some ,Ԑ−NFA (where q0 is the start state), then the result of δ*(q2,aba) is :

A. Φ

B. {q0, q1, q3}

C. {q0, q1, q2}

D. {q0, q2, q3}

19. If w Є L(G), for some grammar G, which of the following holds for w ?

A. w has a parse tree, which tells us the (syntactic) structure of w .

B. w could be a program , an SQL-query, an arithmetic expression, depending on G.

C. w may have several parse trees if L(G) is ambiguous.

D. All of the answers.

20. Which of the following grammars can't be simulated by an FSM ?

A. S → Sa | b B. S → aSb | ab C. S → bX, X → bY, Y → b | aX D. None of the answers

21. Which of the following definitions generate the same language as L, where:

L = {xn y n such that n ≥ 1}

I. G1: E → xEy | xy

II. G2: E → xEy | Ԑ

III. RE1: (x+xyy+)

IIII . RE2: x*xyy*

A. G1 only

B. G1 and G2 only

C. G1 and RE1 only

D. G2 and RE2 only

22. The following right linear grammar G: S→ aS | bS | a | b is equivalent to the regular

expression:

A. (a + b) B. (a + b) (a + b)* C. (a + b) (a + b) D. None of the answers

23. Any string of terminals that can be generated by the following grammar G is__________.

G: S→ XY , X→ aX | bX | a , Y→ Ya | Yb | a

A. has at least one 'b' B. should end in an 'a'

C. has no consecutive a's or b's D. has at least two a's

24. A FSA can recognize:

A. Any left linear grammar B. Only CFG

C. Any right linear grammar D. Both (A) and (C)

25. What can be said about a regular language L over ∑= {a} whose minimal finite state

automation has two states?

A. L must be { a n | n is odd} B. L must be { a n | n is even}

C. L must be {an | n ≥0} D. Either (A) or (B)

26. Regular languages can be recognized by a__________ :

A. NFA B. DFA

C. RE D. All of the answers

27. The grammars G = ( { S }, { 0, 1 }, P , S) where:

P = {S → 0S1, S → 0S, S → S1, S→0}

defines:

A. Non-regular language B. Regular language

C. Both A and B D. None of the answers

28. Consider a grammar G = { { S } , { 0 , 1,+ } , P , S } , where P ={ S→SS | 0S1 | 1S 0 | + }. L(G) is:

A. Machine language B. Regular language

C. Non-regular language D. None of the answers

29. A grammar that produces more than one parse tree for some sentence is called_________:

A. ambiguous B. unambiguous C. regular D. None of the answers

30. If a language L is denoted by a regular expression : ab*a* , then which of the following is a

legal string within L ?

A. λ B. a C. ba D. bbaa

31. If a language L be a set of strings from some alphabet, then kleen closure of L is given as:

A. B. C. D.

32. A PDA can “remember” certain type of information because of the______ memory it uses.

A. ROM B. FIFO Stack C. LIFO Stack D. Queue

33. A grammar to generate the language: { (ab)n | n ≥ 1 } ∪ { (ba)n | n ≥ 1 } is defined by the

following set of production rules :

A. G1: S → S1 | S2, S1 → abS1 | ab, S2 → baS2 | ba

B. G2: S → S1 | S2, Sl → aS1 | ab, S2 → bS2 | ba

C. G3: S → S1, S1→S2| ab, S2 → S1a | ba

D. None of the answers.

34. Which of the following is a primitive regular expression?

A. b* B. 10+

C. (λ+a) D. None of the answers

35. The following grammar has _____ Production rules with _____Variables, and _____Terminals: E → E - T | T, T → T * F | F, F → a | b

A. 3, 3, 2 B. 6, 3, 2 C. 3, 3, 4 D. 6, 3, 4

Question # 2/ [5 marks] Answer with True or False for 5 ONLY of the following:

1. The following regular expressions represent the same language, where a; b are letters in an

alphabet: (a*b*)* = (a + b)*. True

2. Consider the following grammar G, then the string: ((( )( ))) ε L(G).

G: P → Ɛ | ( P ) | P P. True

3. Context-free languages are a larger class of languages that encompasses all regular languages. True

4. DFA's are strictly weaker class than NFA's, i.e., there exists a language that is accepted by an

NFA but is not accepted by any DFA. True

5. (a+λ)* = a+. False

6. 1*0(1*0)* = (1*0)+. False

7. a? = (a+λ) .True

8. Formal languages include Arabic language. False

9. In the Finite Automata the tape can move to the right only . False

10. Moore and Mealy machines are Finite Automata with one final state or more. False

11. In the Mealy machine, the number of output is same number of input. False

12. Moore machine can accept or reject the input string. Ture

Question # 3/ [10 marks]

Given a grammar G that has a set of terminals : {0,1,−}, a set of non-terminals: {N,P}, where N is

the start symbol, and productions given by the following rules:

G: N → 0 | P | P −

P → 1 | P 0 | P 1

a. Is G a regular grammar? Verify your answer.

Sol//

Let's analyze each production:

1. $ N -> 0 $: This is a regular production as it matches the form $ A -> a $.

2. $ N -> P $: This is not a regular production as it does not match the required form.

3. $ N -> P - $: This is not a regular production as it does not match the required form.

4. $ P -> 1 $: This is a regular production as it matches the form $ A -> a $.

5. $ P -> P0 $: This is not a regular production as it does not match the required form.

6. $ P -> P1 $: This is not a regular production as it does not match the required form.

Since not all productions of grammar $ G $ match the form required for a regular grammar, $ G $ is not a regular grammar.

b. Give a DFA that accepts the language generated by G (i.e L(G)).

Sol//

The DFA will have two states: $𝑁$ and $𝑃$ , with transitions defined based on the productions of the grammar. The accepting states correspond to the terminal symbols $0$ and $1$ .

c. Give the DFA that accepts (L(G))^R

Sol//

Let's denote the DFA obtained for $𝐿 (𝐺)$ as $𝑀$ . To obtain the DFA for $(𝐿 (𝐺))^{𝑅}$ , we perform the following steps:

Reverse the direction of transitions in $𝑀$ .
Swap the initial state with the accepting states to designate them as initial states.
Designate the previous initial state of $𝑀$ (which was not an accepting state) as the sole accepting state in the new DFA.

Let's denote the resulting DFA as $𝑀^{𝑅}$ . This DFA will accept the reverse language $(𝐿 (𝐺))^{𝑅}$ .

Question #4/ [10 marks]

Given the following set of transition functions corresponding to some finite state machine M:

δ(S,0) = A, δ(S,1) = A, δ(A,0) = A, δ(A,1) = A, δ(A,+) = B, δ(A,-) = B,

δ(B,0) = B, δ(B,1) = B, δ(B,0) = C, δ(B,1) = C

where: Q= {S,A,B,C}, ∑={0,1,+, -}, F={C}, and S is the start state. Answer each of the following:

a) Is M an NFA or DFA?

Sol//

$M$ is a deterministic finite automaton (DFA)

b) Is L(M) Regular or Context Free language ?

Sol//

$𝐿 (𝑀)$ is a regular language.

c) Give the transition table for M.

Sol//

d) Draw the state transition diagram corresponding to M.

Sol//

e) Give an equivalent grammar G for M such that L(G) = L(M).

Sol//

Question # 5/ [ 10 marks]

Given the following grammar G that defines the language of arithmetic expressions, answer the

questions below:

G: E → E + E | E * E | (E) | Id, Id→a

a) Define G in terms of : T,V, and S .

Sol//

Terminals ( $𝑇$ ): {+, *, (, ), a}
Variables ( $𝑉$ ): {E, Id}
Start symbol ( $𝑆$ ): $𝐸$

b) Is it a regular grammar? Verify your answer.

Sol//

$G$ is not a regular grammar because it contains left-recursive productions ( $𝐸 \to 𝐸 + 𝐸$ and $𝐸 \to 𝐸 * 𝐸$ ), which violates the rules of regular grammars.

c) Is it possible to convert it into an equivalent DFA? Verify your answer.

Sol//

it is not possible to convert $𝐺$ into an equivalent DFA because $𝐺$ is not a regular grammar. Regular grammars correspond to regular languages, which can be recognized by deterministic finite automata (DFA). Since $𝐺$ is not regular, it cannot be represented by a DFA.

d) Is it ambiguous grammar? Verify your answer.

Sol//

$G$ is ambiguous because it allows for multiple parse trees for certain expressions. For example, the expression $𝑎 + 𝑎 * 𝑎$ can be parsed as either $(𝑎 + 𝑎) * 𝑎$ or $𝑎 + (𝑎 * 𝑎)$ , resulting in different interpretations of the expression.