Home > Theory Of Computation > NFA Problem

NFA Problem

NFA Problem – Consider The NFA M Given Below.

Let ‘M’ Be The NFA Obtain From By Interchanging Final And Non- Final States.

Let L And L1

Be The Language Accepted By M And MRespectively Then Which Of The Following Statement Is True.

  1. L=L1
  2. L⊆L1
  3. L1⊆L
  4. L∩L1
  5. L∩L1=Σ*
  6. L∪L1
  7. L∪L1=Σ*

Solution:-

Given NFA ‘M’ Is

He Said Let MBe The NFA From By Interchanging Final And Non-Final States.

 

1 to 7 Are The Statements Given, We Have To See Which One Is True And Which One Is False.

Remember

There Will Be No Complement For NFA, DFA Rules Are Not Applied For NFA.

1) L=L1

Observe M & M1Means ‘M’ Machine Accepts ‘L’ Language And ‘ M1‘Machine Accepts ‘L1‘ Language.If You Observe ‘M’ Machine’s Transitions And ‘M1‘ Machines Transitions Are Different.

Single ‘1’ Is Accepted On ‘A’ Of ‘M’ But Single ‘1’ Is Not Accepted On ‘M1‘ So L & LIs Not Equal.

‘C’ Is Unreachable In ‘M1

‘,’C’ Has Outward Arrow C Is Useless State Actually You Can Remove ‘C’ Because It Is Useless Ignore ‘C’.

 

L=LIs Not True.

2) L⊆L1

L Is The Subset Of L1

Observe M & M1

 

Language ‘L’ Is Accepted By Machine ‘M’

Language ‘L1‘ Is Accepted By Machine ‘M1

 

L⊆L1  Means ‘L’ Language Should Be Accepted By LLanguage.

We Have Seen Single ‘1’ Is Not Accepted In ‘M’ & ‘M1‘ So L Cant Be The Subset Of L1

In SImple Words ‘M’ Machine Language Should Be Accepted By ‘M1‘ Language.

 

‘M’ Language And ‘M1‘ Language Is Different So String In M & MAre Different.

L Language Cant Be The Subset Of LLanguage.

L⊆LIs False.

 

3)  L1⊆L

LIs The Subset Of ‘L’

Means Language L Should Accept The Language L1

 

1,0 Language In ‘M’ In ‘A’ Is Going To Final State And 1,0 Language In ‘M1‘ In ‘B’ Is Going To Non-Final State.

The Language Accepted In ‘M’ And Same Language Is Rejected In M.

 

LIs Not Subset Of L

L1⊆L Is False.

 

4) L∩L1

First Point Here Is Delete Unnecessary Strings From M And M1

The States Which Are Unreachable From Starting State ‘A’ 1 Removed.

If You Observe ‘M’ It Is String Which Contains ‘0’ And Not Accepted By The State ‘B'(Non-Final State)

Means The Strings Which Contains Only 1 Are Accepted In ‘M’.If Not It Goes To Non-Final State ‘B’

 

In ‘M’ String Must Contain At least One ‘0’

In ‘M’ String Does Not Contain ‘0’ But In ‘M1‘ String Must Contain At least One ‘0’

 

L∩L1

Means Strings In L And LShould Not Be Common, If There Are Common Strings In L & L

L∩L1=Φ Is True

 

5) L∩L1=Σ*

L∩L1=Σ* Is Also False,If You Observe L∩L1

 

6) L∪L1

This Is False Because The String In M & MAre Different Which Are Going To Different Final States

 

7) L∪L1=Σ*

L In M Is Accepted And L1

In ‘M1‘ Is Accepted If I Take Union For Both I’ll Get Universal Language Σ*

 

There Is A Rule In DFA If L∪L1=Σ*(Universal Language)

‘M’ Became DFA.

 

I Want You To See Complement Of DFA Examples Which I Explained In Previous Posts.

 

One thought on “NFA Problem

Leave a Reply

Secured By miniOrange