Recent questions tagged finite-automata / GATE Overflow for GATE CSE

0 votes

0 answers

1

Finite Automata Combined with Relation
Let DFA , M = (Q, ∑, δ, q$_0$, F) and Relation R is defined on Q as R:Q$\rightarrow$Q such that pRq iff $\forall$ w ∈ $\Sigma$* [ δ*(p,w) ∈ F $\leftrightarrow$ δ*(p,w) ∈ F OR δ* (p, w) ∉ F $\leftrightarrow$ δ* (q, w) ∉ F] then ____________ A) R is Reflexive B) R is Symmetric C) R is transitive D) None

Let DFA , M = (Q, ∑, δ, q$_0$, F) and Relation R is defined on Q as R:Q$\rightarrow$Q such that pRq iff $\forall$ w ∈ $\Sigma$* [ δ*(p,w) ∈ F $\leftrightarrow$ δ...

jaydip74

23 views

jaydip74 asked 1 day ago

0 votes

0 answers

2

Context Free language sample question
Give a context-free grammar for each of the following languages. Consider, Σ={0,1}. A. The language of strings that start with 1 B. The language of strings of the form WWR C. The language of strings that contain the substring 001 D. The language {0n10n where n ≥ 0} E. ... i, j ≥ 0} J. The language {1i01j | j is a multiple of four or i = 3 + 2j where i, j ≥ 0}

Give a context-free grammar for each of the following languages. Consider, Σ={0,1}.A. The language of strings that start with 1B. The language of strings of the form WWR...

dazeeee

70 views

dazeeee asked Apr 3

0 votes

0 answers

3

#toc

Çșȇ ʛấẗẻ

90 views

Çșȇ ʛấẗẻ asked Feb 24

0 votes

2 answers

4

#Convert the NFA in to equivalent R.E.

Çșȇ ʛấẗẻ

178 views

Çșȇ ʛấẗẻ asked Feb 24

0 votes

0 answers

5

#TOC

Çșȇ ʛấẗẻ

57 views

Çșȇ ʛấẗẻ asked Feb 24

2 votes

2 answers

6

GATE CSE 2024 | Set 2 | Question: 12
Which one of the following regular expressions is equivalent to the language accepted by the $\text{DFA}$ given below? $0^{*} 1\left(0+10^{*} 1\right)^{*}$ $0^{*}\left(10^{*} 11\right)^{*} 0^{*}$ $0^{*} 1\left(010^{*} 1\right)^{*} 0^{*}$ $0\left(1+0^{*} 10^{*} 1\right)^{*} 0^{*}$

Which one of the following regular expressions is equivalent to the language accepted by the $\text{DFA}$ given below?$0^{*} 1\left(0+10^{*} 1\right)^{*}$$0^{...

Arjun

2.6k views

Arjun asked Feb 16

1 votes

2 answers

7

GATE CSE 2024 | Set 2 | Question: 31
Let $\text{M}$ be the $5$-state $\text{NFA}$ with $\epsilon$-transitions shown in the diagram below. Which one of the following regular expressions represents the language accepted by $\text{M}$? $(00)^{*}+1(11)^{*}$ $0^{*}+\left(1+0(00)^{*}\right)(11)^{*}$ $(00)^{*}+\left(1+(00)^{*}\right)(11)^{*}$ $0^{+}+1(11)^{*}+0(11)^{*}$

Let $\text{M}$ be the $5$-state $\text{NFA}$ with $\epsilon$-transitions shown in the diagram below.Which one of the following regular expressions represents the la...

Arjun

2.4k views

Arjun asked Feb 16

0 votes

0 answers

8

Regular expression to finite automata

Çșȇ ʛấẗẻ

222 views

Çșȇ ʛấẗẻ asked Feb 15

3 votes

1 answer

9

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 32
Which of the following sets has the greatest cardinality? The set of real numbers R The set of all functions from R to {0,1} The set of all finite subsets of natural numbers The set of all finite-length binary strings

Which of the following sets has the greatest cardinality?The set of real numbers RThe set of all functions from R to {0,1}The set of all finite subsets of natural numbers...

GO Classes

456 views

GO Classes asked Feb 5

6 votes

1 answer

10

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 24
Let $\mathrm{M}$ be a $8$-state Deterministic Finite Automaton over the alphabet $\{a, b, c\}$. If the language accepted by $\text{M}$ i.e. $\text{L(M)}$ is finite, then the maximum possible cardinality of $\text{L(M)}$ is __________.

Let $\mathrm{M}$ be a $8$-state Deterministic Finite Automaton over the alphabet $\{a, b, c\}$. If the language accepted by $\text{M}$ i.e. $\text{L(M)}$ is finite, then ...

GO Classes

561 views

GO Classes asked Jan 28

3 votes

1 answer

11

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 25
A garage door opens if it ever sees the password $011$ in a transmission. More formally, this FSM takes a bitstring consisting of $\text{0's}$ and $\text{1's}$ as its input, and continually outputs $\text{0's}$ until it sees the substring $011,$ ... Arrow $1 - (0/0)$ Arrow $3 - (1/0)$ Arrow $4 - (1/0)$ Arrow $5 - (1/1)$

A garage door opens if it ever sees the password $011$ in a transmission. More formally, this FSM takes a bitstring consisting of $\text{0's}$ and $\text{1's}$ as its inp...

GO Classes

373 views

GO Classes asked Jan 28

3 votes

1 answer

12

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 15
Consider the following NFA $M$ and say what language is recognised by constructing the machine that recognises the complement of $L(M)$ in $\{a\}^*$. $\emptyset$ $\{a\}^*$ $\{a\}$ $\{\varepsilon\}$

Consider the following NFA $M$ and say what language is recognised by constructing the machine that recognises the complement of $L(M)$ in $\{a\}^*$.$\emptyset$$\{a\}^*$$...

GO Classes

477 views

GO Classes asked Jan 21

8 votes

1 answer

13

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 43
Let $\text{D}$ be a DFA with $n$ states $\& \;\text{N}$ be an NFA with $n$ states. Which of the following is/are true? If $\text{D}$ accepts some string of length $n$, then the language of $\text{D}$ is infinite ... $\mathrm{N}$ accepts some string of length $n-1$, then the language of $\mathrm{N}$ is infinite.

Let $\text{D}$ be a DFA with $n$ states $\& \;\text{N}$ be an NFA with $n$ states. Which of the following is/are true?If $\text{D}$ accepts some string of length $n$, the...

GO Classes

666 views

GO Classes asked Jan 21

4 votes

2 answers

14

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 62
Below you see the transition table of a finite state automaton. The initial state is $0;$ the final state is $4.$ $\emptyset$ denotes the fail state, where no successful transition is possible for the given symbol. Note that when encountering a $b$ in state ... $\mathrm{abbb}^+\mathrm{c}^+\mathrm{c}$ $a b^* b b(c c)^+$

Below you see the transition table of a finite state automaton. The initial state is $0;$ the final state is $4.$ $\emptyset$ denotes the fail state, where no successful ...

GO Classes

351 views

GO Classes asked Jan 13

4 votes

1 answer

15

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 63
This question concerns two languages over the alphabet $\Sigma=\{1,-1\}$ (note that this is an alphabet with just two symbols: $1$ and $-1 ).$ The two symbols are interpreted, in the natural way, as the numbers $1$ and $-1,$ in ... $\text{L}_1$ Only $\text{L}_2$ Both None

This question concerns two languages over the alphabet $\Sigma=\{1,-1\}$ (note that this is an alphabet with just two symbols: $1$ and $-1 ).$ The two symbols are interpr...

GO Classes

577 views

GO Classes asked Jan 13

0 votes

1 answer

16

Find the number of final states in DFA that recognizes L, where L= {w1a w2:|w1|≥3,|w2|≤5}, ∑={a, b} and w1, w2 ∈ ∑ * ______

Hritik1204

323 views

Hritik1204 asked Jan 5

0 votes

1 answer

17

Not Regular language [find out]
Why is C is regular as it non regular as? Please help me with this confusion

Why is C is regular as it non regular as?Please help me with this confusion

Deepak9000

219 views

Deepak9000 asked Nov 27, 2023

0 votes

1 answer

18

Regular grammar

Çșȇ ʛấẗẻ

195 views

Çșȇ ʛấẗẻ asked Nov 22, 2023

0 votes

1 answer

19

#Regular Languages
For a particular input, a turing machine can ‘hang’ on encountering an infinite loop. Why can’t we say the same for any other machine? i.e A DFA or NFA that follows say a*(b). Will the automaton not ‘hang’ if a string $a^n$ where $n \to$ ∞ is fed to it? Isn’t ‘never accepting but progressing’ the same as hanging?

For a particular input, a turing machine can ‘hang’ on encountering an infinite loop. Why can’t we say the same for any other machine? i.e A DFA or NFA that follows...

Mrityudoot

337 views

Mrityudoot asked Oct 21, 2023

0 votes

1 answer

20

Automata and Formal Languages

jam

223 views

jam asked Oct 17, 2023

0 votes

1 answer

21

Please help how to draw dfa

Çșȇ ʛấẗẻ

258 views

Çșȇ ʛấẗẻ asked Oct 2, 2023

0 votes

1 answer

22

TOC Find the language

Çșȇ ʛấẗẻ

117 views

Çșȇ ʛấẗẻ asked Sep 14, 2023

1 votes

1 answer

23

Minimal Finite Automata - Theory of Computation
Consider the set of all binary strings where the difference between the number of 0’s and number of 1’s is even. The minimum number of states in a DFA that accepts the given set is _____________? (kindly explain the approach to this problem)

Consider the set of all binary strings where the difference between the number of 0’s and number of 1’s is even. The minimum number of states in a DFA that accepts th...

stillhere

406 views

stillhere asked Sep 10, 2023

0 votes

2 answers

24

MADE EASY test series
FIND the no of 2 state dfa with the designated initial state possible over {a,b,c} which accept empty language is equal to

FIND the no of 2 state dfa with the designated initial state possible over {a,b,c} which accept empty language is equal to

jugnu1337

349 views

jugnu1337 asked Sep 3, 2023

0 votes

0 answers

25

Theory of computations

Çșȇ ʛấẗẻ

117 views

Çșȇ ʛấẗẻ asked Aug 28, 2023

0 votes

1 answer

26

Theory of computation

Çșȇ ʛấẗẻ

131 views

Çșȇ ʛấẗẻ asked Aug 28, 2023

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true