Theory of computation miscellaneous Easy Questions and Answers | Page - 1

Theory of computation miscellaneous

Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals.
G₁ : S → aSb / T, T → CT | ∈
G₂ : S → bSa \ T, T → cT | ∈
The language L(G₁) ∩ L(G₂) is

1. Finite.
1. Not finite but regular.
1. Context-Free but not regular.
1. Recursive but not context-free.

View Hint View Answer Discuss in Forum

The context free grammar given over alphabets
∑ = {a, b, c}, with S and T are nonterminals.
Given, G₁ : S → aSb | T , T → cT | ∈
G₂ : S → bSa | T , T → cT | ∈
Lets L(G₁) is the language for Grammar (G₁) and L(G₂) is the language for Grammar (G₂).
where L(G₁) = { aⁿ c^m bⁿ | m , n ≥ 0 }
L(G₂) = { bⁿ c^m aⁿ | m , n ≥ 0 }
then L(G₁) ∩ L(G₂) = { aⁿ c^m bⁿ } ∩ { bⁿ c^m aⁿ }
= { c^m | m ≥ 0 } = C^*
Since the only common strings will be those strings with only ‘C’, so the intersection is not finite but regular.

Correct Option: B

The context free grammar given over alphabets
∑ = {a, b, c}, with S and T are nonterminals.
Given, G₁ : S → aSb | T , T → cT | ∈
G₂ : S → bSa | T , T → cT | ∈
Lets L(G₁) is the language for Grammar (G₁) and L(G₂) is the language for Grammar (G₂).
where L(G₁) = { aⁿ c^m bⁿ | m , n ≥ 0 }
L(G₂) = { bⁿ c^m aⁿ | m , n ≥ 0 }
then L(G₁) ∩ L(G₂) = { aⁿ c^m bⁿ } ∩ { bⁿ c^m aⁿ }
= { c^m | m ≥ 0 } = C^*
Since the only common strings will be those strings with only ‘C’, so the intersection is not finite but regular.

Consider the following expression grammar G:
E → E - T | T
T → T + F | F
F → (E) | id
Which of the following grammars is not left recursive, but is equivalent to G?

1. E → E - T | T
  T → T + F | F
  F → (E) | id
1. E → TE '
  E ' → -TE ' | ∈
  T → T + F | F
  F → (E) | id
1. E → TX
  X → -TX | ∈
  T → FY
  Y → + FY | ∈
  E → (E) | id
1. E → TX | (TX)
  X → - TX | +TX | ∈
  T → - id

View Hint View Answer Discuss in Forum

E → E - T |
T → T + F | F
F → ( E ) | id
Using the rule for removal of left recursion is
A → Aα / β
A → βA '
A ' → α A ' / ∈
Then, the given grammar is written as :-
E' → −TE' / ∈
E → +TE '
T ' → + FT ' / ∈
T → FT '
F → (E) | id
Now by putting E ' as X and T ' as Y, then
X → −TX / ∈
E → TX
Y → +FY / ∈
T → FY
F → (E) | id
Hence option (c) is correct.

Correct Option: C

E → E - T |
T → T + F | F
F → ( E ) | id
Using the rule for removal of left recursion is
A → Aα / β
A → βA '
A ' → α A ' / ∈
Then, the given grammar is written as :-
E' → −TE' / ∈
E → +TE '
T ' → + FT ' / ∈
T → FT '
F → (E) | id
Now by putting E ' as X and T ' as Y, then
X → −TX / ∈
E → TX
Y → +FY / ∈
T → FY
F → (E) | id
Hence option (c) is correct.

Consider the following grammar:
stmt - > if expr then expr else expr; stmt | o
expr - > term relop term | term
term - > id | number
id - > a | b | c
number - > [0-9]
where relop is a relational operator (e.g., <, >, ...), o refers to the empty statement, and if, then, else are terminals. Consider a program P following the above grammar containing ten if terminals. The number of control flow paths in P is ________. For example, the program
if e₁ then e₂ else e₃
has 2 control flow paths, e₁ → e₂ and e1 → e₃.

1. 1024
1. 512
1. 128
1. 64

View Hint View Answer Discuss in Forum

The number of control Paths is depends on number of if statement that is 2ⁿ, where, n is the number. of if statements For (2 “if statements”) 2² = 4 control flow Paths are possible :

These four control flow are :
(1) e₁ → e₂
(2) e₁ → e₃
(3) (e₂ if e₄ ) → e₅
(4) (e₃ if e₄ ) → e₅
So, for (10 “if statements”), 2¹⁰ = 1024.
Control flow path are possible. Hence, answer is 1024.

Correct Option: A

The number of control Paths is depends on number of if statement that is 2ⁿ, where, n is the number. of if statements For (2 “if statements”) 2² = 4 control flow Paths are possible :

These four control flow are :
(1) e₁ → e₂
(2) e₁ → e₃
(3) (e₂ if e₄ ) → e₅
(4) (e₃ if e₄ ) → e₅
So, for (10 “if statements”), 2¹⁰ = 1024.
Control flow path are possible. Hence, answer is 1024.

Which of the following decision problems are undecidable?
I. Given NFAs N₁ and N₂, is L(N₁) ∩ L(N₂) = Φ ?
II. Given a CFG G = (N, ∑ , P, S) and a string x ∈ ∑*, does x ∈ L(G) ?
III. Given CFGs G₁ and G₂ is L(G₁) = L(G₂)?
IV. Given a TM M, is L(M) = Φ ?

1. I and IV only
1. II and III only
1. III and IV only
1. II and IV only

View Hint View Answer Discuss in Forum

There is no known algorithm to verify whether the language accepted by TM is empty or not. Similarly there is no algorithm to verify whether language of CFG’s are equivalent.

Correct Option: C

There is no known algorithm to verify whether the language accepted by TM is empty or not. Similarly there is no algorithm to verify whether language of CFG’s are equivalent.

If G is a grammar with productions
S → SaS | aSb | bSa | SS | ∈
where S is the start variable, then which one of the following strings is not generated by G ?

1. abab
1. aaab
1. abbaa
1. babba

View Hint View Answer Discuss in Forum

The given grammar with productions,
S → SaS | aSb | bSa | SS | ∈
Now consider,
S → aSb | bSa | SS | ∈
This grammar generates all strings with equal number of ‘a’ and ‘b’.
Now, S → SaS can only generate strings where ‘a’ is more than ‘b’. Since on left and right of ‘a’ in SaS, S will have only strings with n_a = n_b or n_a > n_b.
Now consider each options
1. S → SS → aSbS → abS → abaSb → abab ,when, S → ∈
2. S → aSb → aSaSb → aaaSb → aaab , when S → ∈
3. S → SS → aSbS → abS → abbSa → abbSaSa → abbaa, when ( S → ∈ )
4. “babba” which is a string with nb > na is not possible to generate by the given grammar.
Hence, option (d) is correct.

Correct Option: D

The given grammar with productions,
S → SaS | aSb | bSa | SS | ∈
Now consider,
S → aSb | bSa | SS | ∈
This grammar generates all strings with equal number of ‘a’ and ‘b’.
Now, S → SaS can only generate strings where ‘a’ is more than ‘b’. Since on left and right of ‘a’ in SaS, S will have only strings with n_a = n_b or n_a > n_b.
Now consider each options
1. S → SS → aSbS → abS → abaSb → abab ,when, S → ∈
2. S → aSb → aSaSb → aaaSb → aaab , when S → ∈
3. S → SS → aSbS → abS → abbSa → abbSaSa → abbaa, when ( S → ∈ )
4. “babba” which is a string with nb > na is not possible to generate by the given grammar.
Hence, option (d) is correct.