ISRO2020-40

Question

Which of the following classes of languages can validate an $\text{IPv4}$ address in dotted decimal format? It is to be ensured that the decimal values lie between $0$ and $255$.

• A. RE and higher
• B. CFG and higher
• C. CSG and higher
• D. Recursively enumerable language

Comments

can we challenge this question as it is not clear what is RE? i thought it is Recursively Enumerable and marked D to be at safer side as it includes all languages, Also can someone prove how D is wrong? even if A is right D can't be wrong

---

Mk Utkarsh

Option D isn't wrong. And this is a poorly framed question. But we have to play along with questions as such if we want PSUs.

If D says Recursively Enumerable, then A by default can't be the same thing, and the abbreviation should mean Regular. (We have to assume it)

Also, question says "classes of languages" but then proceeds with "RE" (not a class of language; assuming Regular Expressions), CFG and CSG are also not classes of languages, but grammars.
Only Option D is a class of languages technically, and it encompasses all the other classes. So it is trivially true, and GATE would never ask such questions.

 

But this is an ISRO question. We have to assume stuff, and since they give options in hierarchy, we'll also have to assume they're asking for the least powerful class of languages that can do the job. For which Regular Languages would be the answer (because IPv4 addresses are finite).

 

Keep in mind the intelligence of the question creators while solving their questions.

---

JashanArora yes i didn't challenge, i was pissed off a little at that time.

Answer 1

Answer: a) RE and higher.

To validate IPV4 in dotted decimal format the values should be between 0-255. We can draw a DFA for it since the values are finite.

For other options if we select them then it means we cannot do it using RE which is false. Thus best option is a).

Comments

What is RE ?? Regular Expression ??

any value not in [0,255] will go to trap state. Then for a state towards Trap state, there will be infinite transition.

How to draw DFA for this

---

@Tuhin Dutta

Why it would be only RE?? 

It is regular which means it is satisfied by CFG,CSG and RE .

right??

So, why not B)?

---

When Reg Expr is satisfying then it is the best answer that's why and option A) says RE and higher. They are not telling only RE.

Answer 2

the dotted decimal values are from 0 to 255 whicn\h means finite . so we can draw DFA which conforms to Regular Language .Also higher languages CFG,CSG,REC will validate IPV4 address on dotted decimal.