Let B consist of all binary strings beginning with a 1 whose value when converted to decimal is divisible by 7 .a)B can be recognized by a deterministic finite state automaton.b)B can be recognized by a non-deterministic finite state automaton but not by a deterministic finite state automaton.c)B can be recognized by a deterministic push-down automaton but not by a non-deterministic finite state automaton.d)B can be recognized by a non-deterministic push-down automaton but not by a deterministic push-down automaton.e)B cannot be recognized by any push down automaton, deterministic or non-deterministic.Correct answer is option 'A'. Can you explain this answer?

Question

Accepted Answer

if it start with 1 it goes to final state

if start with 0 it will go to the reject state

Answer

The given language is the intersection of two regular languages.

Binary strings beginning with 11

Binary strings divisible by 77 (For any integer n,n, divisibility by nn for a binary string can be checked using a finite automata making the language regular.)

Intersection of two regular language is regular (Regular set being closed under intersection).
Correct Answer: A.

Answer

Explanation:

To recognize the language B consisting of all binary strings beginning with a 1 whose value when converted to decimal is divisible by 7, we need to determine the type of automaton that can recognize this language. Let's analyze the given options:

a) B can be recognized by a deterministic finite state automaton:
A deterministic finite state automaton (DFA) is a finite state machine that accepts or rejects strings of symbols and does not have any memory. In this case, the language B consists of binary strings that have a specific mathematical property (being divisible by 7). DFAs are not capable of performing arithmetic calculations, so they cannot check if a binary string is divisible by 7. Therefore, a DFA cannot recognize the language B.

b) B can be recognized by a non-deterministic finite state automaton but not by a deterministic finite state automaton:
A non-deterministic finite state automaton (NFA) is a finite state machine that can be in multiple states at the same time. NFAs are more expressive than DFAs and can recognize certain types of languages that DFAs cannot. However, the language B still requires arithmetic calculations to determine if a binary string is divisible by 7. Therefore, an NFA also cannot recognize the language B.

c) B can be recognized by a deterministic push-down automaton but not by a non-deterministic finite state automaton:
A deterministic push-down automaton (DPDA) is an extension of a DFA that has a stack memory. DPDA can recognize context-free languages, which are more expressive than regular languages (recognized by DFAs). However, the language B is not a context-free language. Checking if a binary string is divisible by 7 requires counting and arithmetic operations, which cannot be performed by a DPDA. Therefore, a DPDA cannot recognize the language B.

d) B can be recognized by a non-deterministic push-down automaton but not by a deterministic push-down automaton:
A non-deterministic push-down automaton (NPDA) is an extension of an NFA that has a stack memory. NPDA can recognize context-free languages like DPDA. However, as mentioned earlier, the language B is not a context-free language. Therefore, an NPDA also cannot recognize the language B.

e) B cannot be recognized by any push-down automaton, deterministic or non-deterministic:
This statement is incorrect. Although the language B cannot be recognized by any of the automata mentioned above, it can be recognized by a more powerful computational model, such as a Turing machine. Turing machines have the ability to perform arithmetic calculations and can recognize languages that are not even recursively enumerable.

Therefore, the correct answer is option 'A' - B can be recognized by a deterministic finite state automaton.

Similar Computer Science Engineering (CSE) Doubts

Let L consist of all binary strings beginning with a 1 such that its value when converted to decimal is divisible by 5. Which of the following is true?

Context-free language can be recognized by

Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S a S b | SS | Which of the following statements is true?

A finite automata over the input alphabet {x,y} is given below. What does the following deterministic finite automata perform?

A minimum state deterministic finite automaton accepting the language L={w | w {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company