Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > Which of the following is true for the langua...
Start Learning for Free
Which of the following is true for the language 
- a)It is not accepted by a Turing Machine
- b)It is regular but not context-free
- c)It is context-free but not regular
- d)It is neither regular nor context-free, but accepted by a Turing machine
Correct answer is option 'D'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
Which of the following is true for the languagea)It is not accepted by...
Turing machine can be designed for ap using the concept of ‘Sieve of Eratosthenes’.
Suppose we are given an integer ‘n’ and we want to find out all the prime numbers less than or equal to ‘n’. We repeat the following steps : We find the smallest number in the list, declare it prime and eliminate all the multiples of that number from the list. We keep doing this until each element has been declared prime or eliminated from the list.
Now, if p = 0 or p = 1, we reject the input. Else, we replace the first and the last ‘a’ with symbol $.
In the above steps, what we do is we find the first non-black symbol from the left. Let this symbol occur at position ‘x’. Suppose ‘x’ is a prime number. If this non-blank symbol is $, input string will be accepted. But, if the symbol is ‘a’, we mark it as a* and replace all the multiples of ‘x’ with the symbol ‘blank’. If at the end, symbol $ is replaced with 'blank’, we reject the input string (because p will be multiple of some ‘x’ in that case). Else, we go back and repeat the steps.
Suppose we are given an integer ‘n’ and we want to find out all the prime numbers less than or equal to ‘n’. We repeat the following steps : We find the smallest number in the list, declare it prime and eliminate all the multiples of that number from the list. We keep doing this until each element has been declared prime or eliminated from the list.
Now, if p = 0 or p = 1, we reject the input. Else, we replace the first and the last ‘a’ with symbol $.
In the above steps, what we do is we find the first non-black symbol from the left. Let this symbol occur at position ‘x’. Suppose ‘x’ is a prime number. If this non-blank symbol is $, input string will be accepted. But, if the symbol is ‘a’, we mark it as a* and replace all the multiples of ‘x’ with the symbol ‘blank’. If at the end, symbol $ is replaced with 'blank’, we reject the input string (because p will be multiple of some ‘x’ in that case). Else, we go back and repeat the steps.
Thus, the input is neither regular nor context-free, but is accepted by a Turing machine.
Please comment below if you find anything wrong in the above post.
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Similar Computer Science Engineering (CSE) Doubts
Top Courses for Computer Science Engineering (CSE)View all
Which of the following is true for the languagea)It is not accepted by a Turing Machineb)It is regular but not context-freec)It is context-free but not regulard)It is neither regular nor context-free, but accepted by a Turing machineCorrect answer is option 'D'. Can you explain this answer?
Question Description
Which of the following is true for the languagea)It is not accepted by a Turing Machineb)It is regular but not context-freec)It is context-free but not regulard)It is neither regular nor context-free, but accepted by a Turing machineCorrect answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 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 of the following is true for the languagea)It is not accepted by a Turing Machineb)It is regular but not context-freec)It is context-free but not regulard)It is neither regular nor context-free, but accepted by a Turing machineCorrect answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Which of the following is true for the languagea)It is not accepted by a Turing Machineb)It is regular but not context-freec)It is context-free but not regulard)It is neither regular nor context-free, but accepted by a Turing machineCorrect answer is option 'D'. Can you explain this answer?.
Which of the following is true for the languagea)It is not accepted by a Turing Machineb)It is regular but not context-freec)It is context-free but not regulard)It is neither regular nor context-free, but accepted by a Turing machineCorrect answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 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 of the following is true for the languagea)It is not accepted by a Turing Machineb)It is regular but not context-freec)It is context-free but not regulard)It is neither regular nor context-free, but accepted by a Turing machineCorrect answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Which of the following is true for the languagea)It is not accepted by a Turing Machineb)It is regular but not context-freec)It is context-free but not regulard)It is neither regular nor context-free, but accepted by a Turing machineCorrect answer is option 'D'. Can you explain this answer?.
Solutions for Which of the following is true for the languagea)It is not accepted by a Turing Machineb)It is regular but not context-freec)It is context-free but not regulard)It is neither regular nor context-free, but accepted by a Turing machineCorrect 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 of the following is true for the languagea)It is not accepted by a Turing Machineb)It is regular but not context-freec)It is context-free but not regulard)It is neither regular nor context-free, but accepted by a Turing machineCorrect answer is option 'D'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Which of the following is true for the languagea)It is not accepted by a Turing Machineb)It is regular but not context-freec)It is context-free but not regulard)It is neither regular nor context-free, but accepted by a Turing machineCorrect answer is option 'D'. Can you explain this answer?, a detailed solution for Which of the following is true for the languagea)It is not accepted by a Turing Machineb)It is regular but not context-freec)It is context-free but not regulard)It is neither regular nor context-free, but accepted by a Turing machineCorrect answer is option 'D'. Can you explain this answer? has been provided alongside types of Which of the following is true for the languagea)It is not accepted by a Turing Machineb)It is regular but not context-freec)It is context-free but not regulard)It is neither regular nor context-free, but accepted by a Turing machineCorrect answer is option 'D'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Which of the following is true for the languagea)It is not accepted by a Turing Machineb)It is regular but not context-freec)It is context-free but not regulard)It is neither regular nor context-free, but accepted by a Turing machineCorrect 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
|
|
Suggested Free Tests
Signup for Free!
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