CODEWITHSUNDEEP
automationcontext-free-grammarregular-languageturing-machinespushdown-automaton
Chaos
Chaos

Reputation: 307

How to determine which class these languages belong to?

{WW} - Decidable but not Context free
{WW^R} - Context Free, but not in Regular
Σ* - Regular language
How can you determine which class they belong to?

Upvotes: 1

Views: 346

Answers (1)

Grijesh Chauhan
Grijesh Chauhan

Reputation: 58271

May be my answer helpful to you:

L1 = {ww | w ∈ {a, b}* }

is not context Free Language because a (Push down Automata) PDA is not possible (even Non-Deterministic-PDA ). Why? suppose you push first w in stack. To match second w with first w you have to push first w in reverse order (either you need to match second w in reverse order with stack content) that is not possible with stack (and we can't read input in reverse order). Although its decidable because be can draw a Turing Machine for L1 that always half after finite number of steps.

L3 = {wwR | w ∈ {a, b}* }

Language L3 is a Non-Deterministic Context Free Language, because n-PDA is possible but Finite Automate is not possible for L3. you can also proof this using Pumping Lemma for Regular Languages.

Σ* - Regular Language(RL)

Σ* is Regular Expression (RE) e.g if Σ = {a, b} then RE is (a + b)* RE is possible only for RLs.

The examples in my question may be more helpful to you.

Upvotes: 1

Related Questions