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

$\mathrm{L}=\left\{\mathrm{x}\mathrm{y},\mathrm{x}\mathrm{x}\mathrm{y}\mathrm{y},\mathrm{x}\mathrm{x}\mathrm{x}\mathrm{y}\mathrm{y}\mathrm{y}\dots \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)

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

Concept:

Regular languages:

Language which can be solved using finite automata are known as regular languages. Finite automata do not have recognition power. Comparison based languages are not regular languages.

Context free languages:

Languages that requires only single stack can be solved using push down automata are known as context free languages.

Explanation:

Given language: {W^a X^b Y^a+b | a, b ≥ 1}

This language can be easily solved by using single stack. It can be easily solved using push down automata.

So, it is a context free language. A context free language is also context sensitive.

For given language,

1) First push all W in the stack.

2) Push all X into the stack

3) With each Y, first pop X from the stack and then pop W from the stack until the string finishes.

4) if stack becomes empty and we reach the end of the string then language is accepted.

Diagram:

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)

Example: No. of a’s at least ‘2’ contains 3 states

No. of a’s at least ‘n’ Contain (n + 1) states

Relationship between regular, context free, linear bounded and recursive and recursive enumerable languages.

Chomsky hierarchy of languages:

Now, as NPDA is more powerful than DPDA. DPDA is a subset of NPDA.

In case of finite automata, both DFA and NFA have same power.

Recursive languages are the subset of recursive enumerable languages.

So, correct relationship is:

L₁, L₂ ⊂ L₃ ⊂ L₄ ⊂ L₅ ⊂ 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.

Length of string: 7 bits

1^st bit is 0, 4^th bit is 1, 7^th is 1

Therefore given string is 0 _ _ 1 _ _ 1.

Only 4 positions (2^nd, 3^rd, 5^th, 6^th) needed to explore whether given string is accepted or not

Number of string possible: 2⁴ = 16

Therefore, string which are accepted by given Finite Automaton: 

0 0 0 1 0 1 1

0 0 1 1 0 1 1

0 1 1 1 0 1 1

0 1 0 1 0 0 1

0 1 0 1 1 1 1

∴ number of strings that are not accepted by F = 16 – 5 = 11

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.

Concept:

The given automaton needs to remember that the string begins with "bba" along with the length of the string. The length of the string should be odd. All the strings which do not begin with "bba" and are of even length must be rejected.

The transition diagram for the given DFA is

Therefore, the number of states = 6.

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

Both languages are equivalent: L₁ = L₂: (0 + 1)^* 111 (0 + 1)^*

If a string consists of 3 consecutive 1’s then it is accepted by both L₁ and L₂ else rejected

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:

${\mathrm{L}}_4={\mathrm{a}}^{\mathrm{n}}{\mathrm{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.