Hi! I got a few questions about the language of Regular Expressions. I would def

Question

Hi! I got a few questions about the language of Regular Expressions. I would definitely give you a POSITIVE rating if your answer works. Thanks a lot!

(note: NFA: non-determinist finite automaton)

Are the following statements true or false? Why? Please prove or disprove each statement.

(a) A language L is regular if some NFA accepts every string that is in the language and some NFA rejects every string that is not in the language.

(b) The language L of strings of the form 'xx' (where 'x' is any string of 0's and 1's) is regular.

(c) The language L of strings of 0's and 1's (where each 1 is followed immediately by two 0's, and the number of 0's is even) is regular.

Explanation / Answer

a) True:

explanation:-

for a language L, if we can able to build finite automata that accepts all the strings in L, then L is regular...

now we have two NFA's in which one accepts all the strings in L, and one rejects all the strings in L...

by using these two we can build machine (finite automata)for given L..

hence L is regular..

b)False

explanation:-

To check whether the given string is in the form of xx, we need a stack to compare...

Finite automata doesn't have the stack to compare...

so...we can't build FA for the given L...

Hence L is not regular...

c)True:

explanation:

given L = strings of 0's and 1's{ where each 1 is followed immediately by two 0's, and the number of 0's is even}

we can build Finite automata M1 for language each 1 s followed immediately by two 0's,

we can build Finite automata M2 for language number of 0's is even

The crossproduct of these two M1 and M2, resulting the final finite automata...

since, we can able to build Finite automata...the given language is regular....

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.