Theory of Computation Test 1

Recursive language is not closed under: Homomorphism, substitution

L = { xⁿyⁿ, n ≥ 1 }

This language generates the string equal number of x and y and x is followed by y

\({\rm{L}} = \left\{ {{\rm{xy}},{\rm{\;xxyy}},{\rm{\;xxxyyy}} \ldots } \right\}\)

Statement i: E → xEy | xy

E → xy

E → xEy → xxyy

E → xEy → xxEyy → xxxyyy

Equal number of x and y and x is followed by y

Statement ii: xy | x⁺xyy⁺

L₁ = {xy, xxyy, xxxyy}

xxxyy cannot be generated by language L.

Statement ii: x⁺y⁺

L₂ = {xy, xxy}

xxy cannot be generated by language L.

• Recursive languages are closed under complementation. Therefore, if L is recursive then L’ is also recursive. Every recursive language is recursively enumerable. Hence statement 4 is correct.
• Recursively Enumerable language are not closed complementation. Therefore, if L is recursively enumerable then L’ may or may not recursively enumerable. If L’ is not recursively enumerable then it cannot be recursive. 

Concept:

If 'k' is the number of states of the NFA, it has 2k subsets of states. Each subset corresponds to one of the possibilities that the DFA must remember, so the DFA simulating the NFA will have 2k states.

Explanation:

k ≤ 2^K

NFA = N^K

and DFA = D, also they are ≥ 1

1 ≤ Nk ≤ D

Right-Linear Grammar:

A grammar G = (V, T, S, P) is said to be right-linear grammar if all the productions are of the form

A → xB

A → x

Where A, B ϵ V, and x ϵ T*

Left-Linear Grammar:

A grammar G = (V, T, S, P) is said to be left-linear grammar if all the productions are of the form

A → Bx

A → x

Where A, B ϵ V, and x ϵ T*

Regular Grammar:

In a regular grammar, at most one variable appears on the right side of any production. Furthermost, that variable must be consistently be either the rightmost or leftmost symbol of the right side of any production.

Given Grammar:

G = ({S, X, Y}, {p, q}, S, P)

S → X, X → qY | ϵ, Y → Xp

Although every production is either in right-linear or left-linear form, the grammar itself is neither right-linear nor left-linear, and therefore it is not a regular.

The give grammar is an example of linear grammar.

• The halting problem is undecidable over Turing machines.
• The halting problem is recursively enumerable but not recursive. we can run the Turing Machine and accept if the machine halts, hence it is recursively enumerable.  

Important Point:

• A recursively enumerable language is a language for which there exists a total Turing machine that accepts it. It may or may not halt for input strings w. if it accepts a string it will halt (enter into the final state) and if it does not accept a string it may or may not enter reject state(will loop infinitely ).
• It is also known as a semi-decidable or partially decidable or Turing recognizable or Turing acceptable language.

• \(L2 - L1 = L2 \cap \;\overline {L1} \)

→ Recursive languages are closed under complementation, hence \(\overline {L1}\) is recursive. Since every recursive language is recursively enumerable. Therefore \(L2 - L1\) is recursively enumerable.

• \(L1 - L3 = L1 \cap \;\overline {L3}\)

→ Recursively enumerable languages are not closed under complementation, hence \(\overline {L3}\) may or may not be recursively enumerable language and so \(L1 - L3\) is always recursively enumerable.

• \(L2 \cap L1\)

→ Recursively enumerable language is closed under intersection.  Hence \(L2 \cap L1\) is recursively enumerable.

The correct answer is option 2 i.e. only 2 and 4.

The language {aibjck | i>j>k} is neither regular nor context-free. Both (2) and (4) are only context-free languages.

The language given by {w | w Є {a,b}*, |w| <= 100} is both regular and context-free.

Concept:

Decidable problems: If there is an algorithm to solve a problem than that problem is known as decidable.

Undecidable problem: These problems does not have any algorithm that gives correct output in finite.

Explanation:

1) The language generated by some CFG contains any words of length less than some given number n.

This is a decidable problem. Language contains words of length less than some number n. It means strings are of finite length. Finiteness is a decidable problem.

2) Let L1 be CFL and L2 be regular, to determine whether L1 and L2 have common elements.

One language is CFL and other is regular. Regular language is also CFL. Equality of Context free languages is undecidable.

3) Any given CFG is ambiguous or not.

Ambiguity problem for any language is undecidable. For ambiguous problems, there does not exits any finite time algorithm that can solve it.

4) For any given CFG G, to determine whether epsilon belongs to L(G)

Smallest string that can be derived from the above given grammar is

S → aabbcc

∴ option 1 and option 3 has been eliminated

Second smallest string that can be derived from the given grammar is

S → aaAbbcc

S → aabbAcc

S → aabbBbbcccc

S → aaBbbbbcccc

S → aaaabbbbcccc

Number of 0’s in w: divisible by 5 = {0, 5, 10, 15, 20, 25, 30, 35, 40…}

Now the number of 0’s in w: not divisible by 5 and divisible by 7 will include elements like {7, 14, 21, 28, 42,…6 3, 77...}

Since we can see that 0, 35, 70, 105 ... is not present. The pattern repeats after 35 states (0 to 34), (35 to 69), and so on... 

Number of states =  35

Tips and Tricks:

Number of states = 5 × 7 = 35

• Emptiness problem for a context sensitive language is undecidable
• Subset problem for a context free language is undecidable.
• Membership problem for a recursive language is decidable.
• I and II are undecidable while III is decidable.

• If L = pn q5m rkn  where k is constant, then it is a deterministic context-free language ∴ L1 = pn q5m r10n can be accepted by deterministic pushdown automaton.
• L2 = p2m qa r2n sb | m = n and a = 2b then L2 = p2m q2b r2m sb it not is a context free language ∴ L2 = p2m qa r2n sb cannot be accepted by non-deterministic pushdown automaton.
• L3 = pa qb rc  sx | a = b = c then L3 = pa qa ra  sx   it is not a context free grammar.

Concept:

Only those strings are accepted which derives from the language.

Explanation:

language: L = {ab, aa, baaa}

String 1: baaaba

Partitions are : baaa, ba

In this, partitions are not possible with strings of the given language. ba remains which is not in the language

String 2: aabaaaa

Partitions are: aa, baaa, a

a is not in the given language. So, it is not in L*.

String 3: baaabaaaabaa

Partitions are: baaa, baaa, ab, aa.

All are possible with the given language. So, it is in L*

String 4: baaabaaa

Partitions are: baaa, baaa.

All are possible with the given language. It is in the language.

• If L₁ is recursive language (REC) then L̅₁ is also REC and recursive language is decidable. B reduces to L̅₁ Since L̅₁ is decidable then B is also decidable and decidable languages are recursive.
• L₂ is recursively enumerable language (REL) but not REC and hence L̅₂ is also not REL. Since L̅₂ reduces to A then A is also not REL.

Statement I:

L₁ = a^mb^m+ncⁿ = a^mb^m bⁿcⁿ, it is accepted by deterministic pushdown automaton and hence it is a deterministic context-free language

Push a onto the stack, if b comes and a is on top of stack pop a, if b comes and stack is empty then push b onto stack. Now if c comes, pop b until stack is empty.

Statement II:

L₂ = aa^r | a ϵ (x, y)^* where ar is a reversal of string a

L₂ is not accepted by deterministic pushdown automaton and hence it is not a deterministic context-free language

Statement III:

L₂ = a^mbⁿcⁿd^m, it is accepted by deterministic pushdown automaton and hence it is a deterministic context-free language

Push a onto the stack, if b comes and a is on top of stack push b, if c comes and b is on top of stack pop b until b gets exhausted from stack and if d comes and a is on top of stack pop a until stack is empty.

Statement IV:

\({\rm{\;}}{{\rm{L}}_4} = {\rm{\;}}{{\rm{a}}^{\rm{n}}}{{\rm{b}}^{{n^2}}}\) it is not accepted by deterministic pushdown automaton and hence it is a deterministic context-free language. L₄ is context sensitive language.