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.

Table for analysis:

Hence option 2 is correct

Important Points:

By convention,

Read the bits for Least significant bits (LSB)

For Input 111 → 000 (overflow bit is discarded)

Since the strings are a part of a finite set whose decimal values lie between 0 and 255, the valid classes of languages fall under the category of RE (regular expression) and higher.

Note that, all the options form valid class of languages but choosing any other option than 1 would mean that the string cannot be verified using a finite automata. Every language that is regular, is by default Context free, context sensitive and recursively enumerable.

• Since L1 is empty.The concatenation of any other language with empty language is always empty.
• Hence L1 L2*  evaluates to be empty language. Hence , L1 L2* = {Φ} .
• a* = {Φ} The kleene closure of empty language always gives null string hence  Φ* = {∈}
• Final answer evaluates to be  {Φ} U {∈} = {∈}.

Concept:

S → aSa | bSb | a | b generates strings like {a, b, aaa, bbb, aba, bab, abbba, ababa, ….) which is the set of all odd length palindromes.

Example of odd length pallindrom.

String:  ababa

Option 1: Incorrect

String: “aa” (Not accepted)

Begins and ends with same symbol but not accepted by given grammar

Option 2 and 4: Incorrect

String: “aa” (Not accepted)

Even length palindrome is not accepted by given grammar

(1) L(A) is regular, its complement is also regular and if it is regular it is also context free.

(2) L ( A ) = ( 11*0 + 0 )( 0 + 1 ) * 0*1* = 1*0 ( 0 + 1 ) *  Language has all strings where each string contains ‘0’.

(3) A is not minimal, it can be constructed with 2 states

(4) Language has all strings, where each string contains ‘0’. ( atleast length one)

The given alphabet contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’. In other words, the NFA accepts a+. Therefore complement of the language accepted by automata is empty string.

• 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.

1. Any combination of strings in set {ab, aa, baa} will be in L*.….1) 1. “abaabaaabaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “ab aa baa ab aa".
2. “aaaabaaaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “aa ab aa aa”
3.  “baaaaabaaaab” cannot be partitioned as a combination of strings in set {ab, aa, baa}.
4.  “baaaaabaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “baa aa ab aa”

Hence, the correct answer is option C.

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.

'000' cannot be accepted. So, '00' when gets another 0 must go to a dead state, q.

So, options A and B are eliminated.

By analyzing options C and D, we can understand that when states like 00, 01, 11 or 10 get an input 1 or 0, the next state is the last two digits of the newly formed string.

11 +0 -> 110 (So, 11 on 0 goes to 10).

01+1 -> 011 (So, 01 on 1 goes to 11).

So option D is correct.

• 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.

Options (B) and (C) are invalid because they both accept ‘b’ as a string which is not accepted by give DFA. (D) is invalid because it accepts "bba" which are not accepted by given DFA.

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.