Question 21
Which of the following is a universal Turing-machine property?
Detailed Solution
A UTM simulates other TMs from their finite encodings.
✓ Saved
GATE CSE Turing Machines, RE Languages & Undecidability – TOC Practice Test | Set 1
Your score
0/100
0 answered
Correct 0
Incorrect 0
Unanswered 100
Accuracy 0%
Question 22
Under the standard configuration notation u q v, which symbol is scanned by the head?
Detailed Solution
The notation places the current state between the portion left of the head and the portion beginning at the scanned symbol.
✓ Saved
Question 23
Which operation is guaranteed to preserve recursive languages?
Detailed Solution
Recursive languages are closed under complement, as well as union, intersection, concatenation, and star.
✓ Saved
Question 24
Which operation is NOT guaranteed to preserve RE languages?
Detailed Solution
RE is closed under union, intersection, and concatenation, but not complement.
✓ Saved
Question 25
Which operation preserves CFLs when one operand is regular?
Detailed Solution
CFLs are closed under intersection with regular languages.
✓ Saved