Theory of Computation Test 3

Operation under which context free language is closed: Union, Kleene Closure and Concatenation.

L₁^* and L₂^* is a context free language

→ \({L_1} \cup \;{L_2}\) is a context free language

→ \(L_1^* \cup \;L_2^*\) is a context free language

→ L₁.L₂ is context free ∴ (\({L_1}.{L_2}\))^* is a context free language

Operation under which context free language is not closed: Intersection, complementation, set difference

The given grammar G generates the language having equal number of x’s and y’s

Option 1:

String: xxy

L = {xⁿyⁿ : n ≥ 0} cannot generate.

Option 2:

String: yx

L = {xⁿy^m : n ≥ 0, m ≥ 0} cannot generate

Option 4:

String: xxyxyy

Data

language {a^mbⁿc^m+n | m, n ≥ 1}

Explanation

It is not regular.

It requires memory element for recording the occurrences of a and b to verify number of c. Regular languages cannot have such dependencies.

It is context free

It can be verified using stack within the following steps.

1. Push a’s on to the stack
2. Push b’s on to the stack
3. Parsing through c’s, for every c encountered all the b’s first, and then all the a’s.
4. If nothing is left in the stack after parsing through c’s is done, then the string accepted belongs to this language.

A context grammar is said to be in Greibech Normal Form if all the productions have the form

S → xA

where x ϵ T and x ϵ V^*

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

Option A: Not in GNF. Since production S → AB is not in GNF

Option B: Not in GNF. Since production A → ϵ is not in GNF

Option C: Not in GNF. Since production S → Aa is not in GNF

If L is a context-free language and R is a regular language, L-R is also a context-free language. It is because if R is regular, then R' is also regular. L-R is equivalent to L\(∩\)R'. We know that if L is a CFL and R is a regular language then L\(∩\)R is a CFL. Therefore, L\(∩\)R' is also a CFL making L-R a CFL.

Therefore, S1 is false

Context-free languages are closed under positive closure or (Kleen plus)

Therefore S2 is true

Context-free languages are closed under reversal.

Therefore S3 is false

L = { wcw^r : w ϵ {a, b}^*} is a deterministic context free language. Since center is known, that is, c.

Before c push the terminal onto a stack and after c match and pop.

G₁ : S → aSb|bSa|aa

gives a language G₁ = {number of a = number of b + 2}

G₂ : S → aSb|bSa|SS|λ

gives a language G₂ = {number of a = number of b}

G₃ : S → aSb|bSa|SS|a

gives a language G₃ = {number of a > = number of b + 1}

G₄: S → aSb|bSa|SS|SSS|λ

gives a language G₄ = {number of a = number of b}

Hence, G₂ and G₄ are equivalent.

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

Calculation:

S → XA

A → YB

B → x

X → BC

C → BD

D → y

Y → XE

E → z

Option 1 is false: CFL is closed under reversal. Therefore, L^R₁ is a CF:

Option 2 is false: DCFL is not closed under reversal. Therefore, L^R₂ is not DCFL.

If a language is DCFL then it is CFL but vice versa is not true.

Concept

A problem is said to be Decidable if we can always construct a corresponding algorithm that can answer the problem correctly. Based upon this property, problems are classified as

1. Decidable
2. Semi-decidable
3. Undecidable

Explanation:

Statement i: Decidable

Membership problem in CFL is decidable using CYK algorithm to check the membership.

Statement ii: Undecidable

To check whether a given CFL is regular or not in undecidable.

Statement iii: Decidable

To determine whether an FA halts on all inputs or not is decidable because we have final and non-final states in FAs that indicate whether the input string is accepted or not.

Statement iv: Undecidable