Which among the following cannot be accepted by a regular grammar?a)L ...
There exists no finite automata to accept the given language i.e. 0n1n. For other options, it is possible to make a dfa or nfa representing the language set.
A Non-Regular Grammar
may or may not produce a Regular Language
Hence, the correct answer is Option D
You can go through more such questions by going through the link:
View all questions of this test
Which among the following cannot be accepted by a regular grammar?a)L ...
Explanation:
Regular Grammar:
A regular grammar is a formal grammar that generates regular languages. A regular language is a language that can be expressed using a regular expression or a finite automaton.
Given options:
a) L is a set of numbers divisible by 2
- This can be expressed using a regular grammar as it is a regular language.
b) L is a set of binary complement
- This can be expressed using a regular grammar as it is a regular language.
c) L is a set of string with odd number of 0
- This can be expressed using a regular grammar as it is a regular language.
d) L is a set of 0^n1^n
- This language cannot be expressed using a regular grammar.
Explanation for option d:
The language L is a set of strings of the form 0^n1^n, where n is any positive integer. This language is not a regular language, thus it cannot be expressed using a regular grammar. This can be proved using the pumping lemma for regular languages.
Pumping lemma:
The pumping lemma for regular languages states that if a language L is regular, then there exists a constant n such that any string w in L with length greater than or equal to n can be divided into three parts, w = xyz, such that:
- |xy| ≤ n
- |y| ≥ 1
- for all i ≥ 0, xy^iz ∈ L
Using the pumping lemma, we can prove that the language L = {0^n1^n | n ≥ 1} is not a regular language.
Proof:
Assume that L is a regular language. Then, there exists a constant n such that the pumping lemma holds for all strings in L with length greater than or equal to n.
Let w = 0^n1^n be a string in L with length greater than or equal to n. By the pumping lemma, we can divide w into three parts, w = xyz, such that:
- |xy| ≤ n
- |y| ≥ 1
- for all i ≥ 0, xy^iz ∈ L
Since |xy| ≤ n, we know that y contains only 0's. Let y = 0^k, where 1 ≤ k ≤ n. Then, x = 0^(n-k) and z = 1^n.
Now, consider the string xy^2z. This string is of the form 0^(n+k)1^n, which is not in L. Thus, the pumping lemma does not hold for the string w = 0^n1^n, which contradicts our assumption that L is a regular language.
Therefore, the language L = {0^n1^n | n ≥ 1} is not a regular language and cannot be expressed using a regular grammar.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).