Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > Which among the following cannot be accepted ...
Start Learning for Free
Which among the following cannot be accepted by a regular grammar?
- a)L is a set of numbers divisible by 2
- b)L is a set of binary complement
- c)L is a set of string with odd number of 0
- d)L is a set of 0n1n
Correct answer is option 'D'. Can you explain this answer?
Most Upvoted Answer
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.
Free Test
FREE
| Start Free Test |
Community Answer
Which among the following cannot be accepted by a regular grammar?a)L ...
Regular Grammar and 0^n1^n
Regular grammars are a type of formal grammar used in formal language theory. They consist of a set of production rules that describe all possible strings in a given formal language. Regular grammars can generate regular languages, which are a type of formal language that can be recognized by a finite automaton.
0^n1^n
The language L = {0^n1^n | n ≥ 0} consists of all strings of the form 0^n1^n, where n is a non-negative integer. In other words, the number of 0s in the string is equal to the number of 1s in the string.
Why 0^n1^n cannot be accepted by a regular grammar?
- Regular grammars are limited in their ability to handle languages with nested structures or balancing properties, such as the language 0^n1^n.
- In the language 0^n1^n, each 0 must be followed by a corresponding 1, which requires some form of memory or counting mechanism to keep track of the number of 0s.
- Regular grammars do not have the ability to perform this kind of counting or matching of nested symbols, as they are equivalent in power to finite automata, which have limited memory capabilities.
- As a result, the language 0^n1^n cannot be described by a regular grammar, and more powerful formalisms such as context-free grammars or pushdown automata are required to generate or recognize this language.
In conclusion, the language 0^n1^n cannot be accepted by a regular grammar due to its nested structure and the counting requirements for matching 0s and 1s.
Regular grammars are a type of formal grammar used in formal language theory. They consist of a set of production rules that describe all possible strings in a given formal language. Regular grammars can generate regular languages, which are a type of formal language that can be recognized by a finite automaton.
0^n1^n
The language L = {0^n1^n | n ≥ 0} consists of all strings of the form 0^n1^n, where n is a non-negative integer. In other words, the number of 0s in the string is equal to the number of 1s in the string.
Why 0^n1^n cannot be accepted by a regular grammar?
- Regular grammars are limited in their ability to handle languages with nested structures or balancing properties, such as the language 0^n1^n.
- In the language 0^n1^n, each 0 must be followed by a corresponding 1, which requires some form of memory or counting mechanism to keep track of the number of 0s.
- Regular grammars do not have the ability to perform this kind of counting or matching of nested symbols, as they are equivalent in power to finite automata, which have limited memory capabilities.
- As a result, the language 0^n1^n cannot be described by a regular grammar, and more powerful formalisms such as context-free grammars or pushdown automata are required to generate or recognize this language.
In conclusion, the language 0^n1^n cannot be accepted by a regular grammar due to its nested structure and the counting requirements for matching 0s and 1s.
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Similar Computer Science Engineering (CSE) Doubts
Top Courses for Computer Science Engineering (CSE)View all
Top Courses for Computer Science Engineering (CSE)
Question Description
Which among the following cannot be accepted by a regular grammar?a)L is a set of numbers divisible by 2b)L is a set of binary complementc)L is a set of string with odd number of 0d)L is a set of 0n1nCorrect answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2025 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Which among the following cannot be accepted by a regular grammar?a)L is a set of numbers divisible by 2b)L is a set of binary complementc)L is a set of string with odd number of 0d)L is a set of 0n1nCorrect answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2025 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Which among the following cannot be accepted by a regular grammar?a)L is a set of numbers divisible by 2b)L is a set of binary complementc)L is a set of string with odd number of 0d)L is a set of 0n1nCorrect answer is option 'D'. Can you explain this answer?.
Which among the following cannot be accepted by a regular grammar?a)L is a set of numbers divisible by 2b)L is a set of binary complementc)L is a set of string with odd number of 0d)L is a set of 0n1nCorrect answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2025 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Which among the following cannot be accepted by a regular grammar?a)L is a set of numbers divisible by 2b)L is a set of binary complementc)L is a set of string with odd number of 0d)L is a set of 0n1nCorrect answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2025 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Which among the following cannot be accepted by a regular grammar?a)L is a set of numbers divisible by 2b)L is a set of binary complementc)L is a set of string with odd number of 0d)L is a set of 0n1nCorrect answer is option 'D'. Can you explain this answer?.
Solutions for Which among the following cannot be accepted by a regular grammar?a)L is a set of numbers divisible by 2b)L is a set of binary complementc)L is a set of string with odd number of 0d)L is a set of 0n1nCorrect answer is option 'D'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE).
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of Which among the following cannot be accepted by a regular grammar?a)L is a set of numbers divisible by 2b)L is a set of binary complementc)L is a set of string with odd number of 0d)L is a set of 0n1nCorrect answer is option 'D'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Which among the following cannot be accepted by a regular grammar?a)L is a set of numbers divisible by 2b)L is a set of binary complementc)L is a set of string with odd number of 0d)L is a set of 0n1nCorrect answer is option 'D'. Can you explain this answer?, a detailed solution for Which among the following cannot be accepted by a regular grammar?a)L is a set of numbers divisible by 2b)L is a set of binary complementc)L is a set of string with odd number of 0d)L is a set of 0n1nCorrect answer is option 'D'. Can you explain this answer? has been provided alongside types of Which among the following cannot be accepted by a regular grammar?a)L is a set of numbers divisible by 2b)L is a set of binary complementc)L is a set of string with odd number of 0d)L is a set of 0n1nCorrect answer is option 'D'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Which among the following cannot be accepted by a regular grammar?a)L is a set of numbers divisible by 2b)L is a set of binary complementc)L is a set of string with odd number of 0d)L is a set of 0n1nCorrect answer is option 'D'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Signup to solve all Doubts
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup