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

33 views

jaydip74 asked 2 days 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

73 views

dazeeee asked Apr 3

0 votes

0 answers

3

#toc

Çșȇ ʛấẗẻ

91 views

Çșȇ ʛấẗẻ asked Feb 24

0 votes

2 answers

4

#Convert the NFA in to equivalent R.E.

Çșȇ ʛấẗẻ

180 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

Çșȇ ʛấẗẻ

224 views

Çșȇ ʛấẗẻ asked Feb 15

0 votes

0 answers

9

DFA construction
Each of the following languages is the complement of a simpler language. In each part, construct a DFA for the simpler language, then use it to give the state diagram of a DFA for the language given. In all parts, Σ = {a, b}. 1- {w| w does not contain the substring ab} 2- {w| ... neither the substrings ab nor ba} 4- {w| w is any string not in $a^{*}\cup b^{*}$ } ( ∪ is the union )

Each of the following languages is the complement of a simpler language.In each part, construct a DFA for the simpler language, then use it to give the state diagram of a...

rania

125 views

rania asked Feb 14

0 votes

1 answer

10

State diagram
Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}. 1- {w| w starts with 0 and has odd length, or starts with 1 and has even length}

Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}.1- {w| w starts with 0 and has odd length, or starts with 1 and has e...

rania

149 views

rania asked Feb 14

3 votes

1 answer

11

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

12

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

564 views

GO Classes asked Jan 28

3 votes

1 answer

13

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

375 views

GO Classes asked Jan 28

3 votes

1 answer

14

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

15

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

670 views

GO Classes asked Jan 21

4 votes

2 answers

16

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

352 views

GO Classes asked Jan 13

4 votes

1 answer

17

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

579 views

GO Classes asked Jan 13

0 votes

1 answer

18

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

326 views

Hritik1204 asked Jan 5

0 votes

1 answer

19

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

20

Regular grammar

Çșȇ ʛấẗẻ

196 views

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

0 votes

1 answer

21

#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

338 views

Mrityudoot asked Oct 21, 2023

0 votes

1 answer

22

Automata and Formal Languages

jam

224 views

jam asked Oct 17, 2023

0 votes

1 answer

23

Please help how to draw dfa

Çșȇ ʛấẗẻ

259 views

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

0 votes

1 answer

24

TOC Find the language

Çșȇ ʛấẗẻ

117 views

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

1 votes

1 answer

25

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

409 views

stillhere asked Sep 10, 2023

0 votes

2 answers

26

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

27

Theory of computations

Çșȇ ʛấẗẻ

117 views

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

0 votes

1 answer

28

Theory of computation

Çșȇ ʛấẗẻ

133 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