Theory of Computation Test 2

Concepts

\({{\rm{L}}^{\rm{*}}} = {{\rm{L}}^0} \cup {{\rm{L}}^1} \cup {{\rm{L}}^2} \cup {{\rm{L}}^3} \cup {{\rm{L}}^4} \ldots \ldots .{{\rm{L}}^{\rm{k}}} \cup {{\rm{L}}^{{\rm{k}} + 1}} \ldots \ldots \ldots \)

For any language \({{\rm{L}}^0} = \epsilon\)

Concatenation of \({\rm{\Phi }}\) with any other language is \({\rm{\Phi }}\). It works as 0 in multiplication.

And for \({{\rm{L}}^{\rm{k}}} = {\rm{L}}.{\rm{L}}.{\rm{L}}.{\rm{L}}.{\rm{L}}.{\rm{L}}.{\rm{L}} \ldots \ldots \ldots {\rm{\;L}}\) language is concatenated K- times.

Data:

 L₁ = Φ, L₂ = {a}

Calculation:

\({L_1}L_2^* \cup L_1^* = \;?\)

\({{\rm{L}}_1}\) concatenated with \(L_2^*\) and whole thing union with \(L_1^*\).

First \({\rm{\;L}}_1^{\rm{*}} = {\rm{\;\;}}{\phi ^0} \cup {\phi ^1} \cup {\phi ^2} \ldots \ldots {\rm{\;}}\)  \(= \epsilon \cup \phi \cup \phi \ldots \ldots = \left\{ \epsilon \right\}.\)

Similarly, \({\rm{L}}_2^{\rm{*}} = {\left\{ {\rm{a}} \right\}^0} \cup {\left\{ {\rm{a}} \right\}^1} \cup {\left\{ {\rm{a}} \right\}^2} \ldots \ldots {\rm{\;}} = \epsilon \cup \left\{ {\rm{a}} \right\} \cup \left\{ {{\rm{aa}}} \right\} \ldots \ldots .. = {{\rm{a}}^{\rm{*}}}\)

\({{\rm{L}}_1}{\rm{L}}_2^{\rm{*}} \cup {\rm{L}}_1^{\rm{*}} = {\rm{\Phi \;}}{{\rm{a}}^{\rm{*}}} \cup \left\{ \epsilon \right\} = \left\{ \epsilon \right\}\)

Let L₁ = dec(s) mod 7 = 1 and L₂ = dec(s) mod 11 = 3

L₁ and L₂ both are regular language

L = L₁ ∩ L₂

Regular language is closed under intersection

Therefore, L is regular.

Given grammar is generating string of type: {0, 000, 00000,0000000…...}

1) L((00) * 0 + (11) * 1)

This language generating string with combination of 0’s and 1’s. But given grammar is not generating any string composed of 1’s.

2) L(0(11) * + 1(00) * )

This language is not generating string which contains three 0’s together. Also, it is generating strings which contains 1 in it. So, it is not correct option.

3) L((00) * 0)

It is generating strings of type: {0, 0³, 0⁵, 0⁷,.}. These set of strings is similar to the one generating from given grammar. So, this language is generated by given grammar.

4) L(0(11) * 1)

It is incorrect because it is generating strings which contains 1 which is not the case with given grammar. 

Concept:

Language that is accepted by Turing machine is known as recursive enumerable language.

Explanation:

Turing machine accepts the language which can enumerate all the valid strings and reject all invalid strings.

Here it is given that if any string of a language L can be effectively enumerated by an enumerator in lexicographic order, it means if Turing machine accepts the string, it halts in the final state. If it does not accept the string, then it halts in a non-final state. It means language is recursive. A recursive language is also recursive enumerable.

Concepts:

A context-free grammar is in Chomsky Normal Form if all productions are of the form

A → BC or A → a

{A, B, C} ϵ V and a ϵ T

V is variable(non-terminal) and a is terminal

Data:

x = 101

n → number of productions required to generates string of length x.

Formula:

n = 2x – 1

where x is the length of the string

Calculation:

n = 2(101) – 1

∴ n = 201

S → AB

S → aAbB

S → aaAbbB

S → aaaAbbbB

.

.

.

S → aⁿbⁿcBd

S → anbnccBdd

S → anbncccBddd

.

.

.

S → anbncmdm 

Therefore, the language produced will be anbncmdm / n, m >= 1.

Let q₀ and q₁ be the two states

Let designated initial state be q₀ and designated final state be q₁

Transition Table:

	x	y
→ q0	q0/ q1	q0/ q1
*q1	q0/ q1	q0/ q1

 

Explanation:

In initial state (q₀), on seeing x, it can go to q₀ or q₁. Similarly, on seeing y it can go to q₀ or q₁

In final state (q₀), on seeing x, it can go to q₀ or q₁. Similarly, on seeing y it can go to q₀ or q₁

Number of DFA possible = 2 × 2 × 2 × 2 = 16

Option 1: (00 + (11)*0)

This regular expression generates the strings like:

{0, 00, 000, 110, 11011, 11110, 11000, …} .

It is not generating 1101 because after every 11 there is a single 0 possible but a single 1 is not possible in any case.

Option 2: 1(0 + 1)*101

It is generating strings of type: {1101, 10101, 11101, 101101, ………}.

It contains the string 1101, so not the correct answer.

Option 3: (10)* (00 + 11)* (01)*

This regular expression is generating strings of type: {ϵ, 10, 00, 11, 01, 1000, 1011, 1001, 1101…….}.

It is possible to get 1101 in this expression. So, it is the not correct answer.

Option 4: 110*(0 + 1)

In this, set of strings that are possible are: {110, 111, 1100, 1101, 11001,……..}.

So it is generating the string 1101. So, it is not the correct answer.

Concept:

Inherently ambiguous language: A context free language is inherently ambiguous if every context free grammar for that language is ambiguous.

Explanation:

If we get any one unambiguous grammar for each of the option given above, then that language will not be inherently ambiguous.

Case 1:

\({L_1} = \left\{ {{a^n}{b^n}{c^m}} \right\} \cup \left\{ {{a^n}{b^m}{c^m}} \right\},\;n,\;m \ge 0\)

This is inherently ambiguous language. There does not exist any unambiguous grammar for this. It is somewhat similar to the language L = {aⁱb^jc^k | i = j or j = k} . It has a common subset aⁿbⁿcⁿ.

\({L_2} = \{ w{w^R}|w \in \left\{ {a,\;b} \right\}*\} \) Where R represents reversible operation.

This is not inherently ambiguous language. An unambiguous grammar exists for it:

S -> aSa | bSb |  λ

The palindromes are a set of strings that read the same backward as forward. 

The inclusion of the productions P → 0, P → 1 includes the strings 0 and 1 which are palindromes in themselves. Also, these productions can be used to generate the odd length palindromes. 

Using production P → ε, even length palindromes can be generated.

• {wanbnwR |w ϵ {a, b}*, n ≥ 0} is accepted by a non-deterministic pushdown automaton and hence it is a context-free language
• {wwR |w ϵ {a, b}*} is accepted by a non-deterministic pushdown automaton and hence it is context-free language.
• {wanwRbn|w ϵ {a, b}*, n ≥ 0} is not accepted by a pushdown automaton and hence it is not a context-free language.
• i = n, 2n, 3n, 4n, etc. forms and arithmetic series. anbn, anb2n and anb3n is accepted by a deterministic pushdown automaton and context-free language are closed under union and hence anbn ∪ anb2n ∪ anb3n is a context-free language. Hence {anbi |i ϵ {n, 3n, 5n}, n ≥ 0} is a context-free language.

• In L1, p’s in the string x should be divisible by 10 (N(p) % 10 = 0), and the number of q’s in the string x should be divisible by (N(q) % 15) = 0).Therefore, x = (10 × 15) = 150 states will be needed to minimum DFA accepting the given language
• In L2, a’s in the string x should be divisible by 10 and 15 (N(a) % 10 = 0 and N(a)%15). In the case of the same symbol, LCM is taken. Therefore, y = LCM(10, 15) = 30 states will be needed to minimum DFA accepting the given language.

Therefore, value = x – y = 150 – 30 = 120 

undecidable

Whether a Turing Machine accepts a given language (here, L(M) = { 00, 11 } ) is Non-trivial question, so by Rice’s theorem it is Undecidable problem.

So, {M | M is a Turing Machine and L(M) = { 00, 11 } } is Undecidable.

Option 2: decidable

For an input whose length is less than 200 on which Turing machine halts or not can be decidable by running Turing machine for 200 steps.

So, { M | M is a Turing Machine and there exists an input whose length is less than 200, on which M halts } is Decidable.

Option 3: decidable

{ M | L(M)  is recognized by a Turing Machine having even number of states }

This is a Trivial property because for any recursively enumerable language we have a TM and even if that TM is having odd number of states we can make an equivalent TM having even number of states by adding one extra state. Thus, this set equals the set of recursively enumerable languages and hence Decidable.

Option 4: decidable

If language L is in NP class, then L is Turing Decidable (Recursive) because NP class is the subset of recursive.

Also, P ⊆ NP ⊆ Recursive (Turing Decidable) .

Important Theorem:

Rice’s Theorem - 

• Any “non-trivial” (answer not known) property of the language recognizable by a Turing machine (recursively enumerable language) is Undecidable.
• Any “trivial” property is always Decidable because the decision is known ahead and that is why the property is trivial.

L₁ : { aⁿ b^m a^k | k = mn and k, m, n ≥ 1 } is not CFL, since we cannot implement multiplication of 2 variables with single stack.

L₂ : { a^{m + n} b^{n + m} c^m | n, m ≥ 1 } is not CFL, since here more than 1 comparison on single variable( ‘m’ ) present. Hence cannot be implement by single stack.

 L₃ : { aⁿ bⁿ c^m | m < n and m, n ≥ 1 } is not CFL, since more than 1 comparison are present simultaneously i.e, after comparison of n = n, we left with c^m and we cannot compare m < n or not.

So, All language is not CFL i.e, L₁ , L₂ and L₃ are not context free.

• If B is recursive language (REC) then B’ is also REC and recursive language is decidable. Y reduces to B Since B is decidable then Y is also decidable and decidable languages are recursive.
• A is recursively enumerable language (REL) but not REC and hence A’ is also not REL. Since A’ reduces to X then X is also not REL.

.Concept:

Recursive languages are closed under Union, Complement,  Concatenation and Kleene star

Explanation

Let L1 and L2 be recursive languages.

• \(L_1 \cup L_2\)

→ Recursively enumerable languages are under union operation, hence \(L_1 \cup L_2\)  is recursive

• \( \overline {L_1} \)

→ Recursive languages are closed under complementation operation, hence \(\overline {L_1}\) is recursive.

• \(L_1 .L_2\)

→ Recursively enumerable languages are closed under concatenation operation, hence \(L_1 .L_2\) is recursive.

• \({L_1}^+\)

→ Recursive languages are closed under Kleene star operation, hence \({L_1}^+\) is recursive

Concept: Property of context-free languages is:

Context-free languages are closed under union and difference but not closed under complementation and intersection.

Explanation:

Option 1) L1 ∪ L2 is context-free

As context-free languages are closed under union. So it is correct.

Option 2).  L̅1 is context-free

L1 is a context-free language. According to the property, its complement can’t be context-free.

Option 3) L1 – R is context-free

As the difference of a context-free language with regular is context-free. So, it is correct.

Option 4) L1 ∩ L2 is context-free

It violated the context-free language property. The intersection of two CFL’s is not CFL. So, it is incorrect. 

Concept:

Union of a Regular language and a Deterministic Context-Free Language (DCFL) is a DCFL.

Explanation:

Option 1: FALSE.

L is not a regular grammar from the union property.

Option 2: TRUE.

L = {an |n ≥ 0} ∪ {anbn| n ≥ 0}

{an |n ≥ 0} is a regular language and {anbn| n ≥ 0} is a DCFL and hence, there Union would be a DCFL.

Option 3: FALSE.

L is DCFL then it is CFL too.

Option 4: TRUE

L cannot be LL(k) for any number of look-ahead. LL(k) cannot conclusively distinguish that whether the string to be parsed is from an or from anbn. Both have a common prefix.

Emptiness problem for a context sensitive language is not decidable.

Option 2:

Completeness problem for a context free language in not decidable.

Option 3:

Finiteness problem for a deterministic context free language is decidable.

Option 4:

Membership problem for a recursive language is decidable.

(i) ((01)*(10)*)*

It generates the strings of type {ϵ, 01, 10, 0110, 0101, 1001, 1010, 010110, 01011010,……..}

(ii) (10 + 01)*

Set of strings that are generated by the regular expression:

{ ϵ , 10, 01, 1010, 0101, 0110, 1001, 101010, 010101,………..}

(iii) (01)* + (11)*

Strings that are generates with this expression are:

{ ϵ , 01, 11, 0101, 1111, 010101, 111111,………. }

(iv) (0* + (11)* + 0*)*)

Strings that are generated with this regular expression:

{ ϵ , 0, 11, 00, 000, 011, 110, 0110, 00110, 01100,……….}

Regular expression of first two options are equal, Therefore only 2 is equivalent rest all are not equivalent.