132 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
1
answer
85
views
Do I need a closing X for this language? [closed]
Design a context-free grammar (CFG) that generates all strings over {a, b, c} that contain at least one a, one b, and one c. Define the rules of the CFG.
So I wrote this down:
S -> XaXbXc | XaXcXb |...
0
votes
1
answer
257
views
DFA for input starting with "1", and having "11" in it. Why it doesn't accept this input?
I'm trying to make a Deterministic Finite Automaton (DFA) to accept binary strings that start with "1" and have a substring "11" in it, over {0,1}.
Here is the DFA I created:
...
1
vote
1
answer
348
views
Turing Machine that outputs the number of a's and b's in binary representation
I'm trying to design a Turing Machine that takes as input a word formed by symbols of the alphabet Σ = {a, b} and counts, in binary, the occurrences of symbol a and the occurrences of symbol b.
...
0
votes
0
answers
47
views
recognizing a date in the form: 03/02 for February 3 , For simplicity, we consider that each month is made up of 30 days
this is the code :
package Tp2;
import java.util.Date;
import java.util.Scanner;
public class EX2_Date_forme {
public static void main(String[] args) {
Scanner sc = new Scanner(System....
2
votes
1
answer
561
views
Deterministic automaton whose input length is divisible by 3 or 5?
I only have one letter available as a language (e.g.: x). If I now enter "xxx" or "xxxxx" then the machine should accept this input because in the former case the length is 3 and ...
0
votes
1
answer
65
views
How is it practically possible to compute an automaton inside a function and then return it?
I'm trying to follow Cormen - Algorithms, 3rd edition. Specifically, Chapter VII, 32 "String Matching". In general, I find this book extremely hard to follow, due to the abundance of math-...
1
vote
1
answer
654
views
How to simplify/generalize a Finite State Machine (FSM) for a vending machine?
I have enrolled into course of computational methods, and currently we are reviewing automata and regular expressions. In one of the course assignments we were asked to design a finite state automata ...
user avatar
user19921500
0
votes
2
answers
3k
views
A NFA accepting ;anguages whose final digit didn't appear before
Give a non-deterministic finite automata(NFA) which accepts the following language:
The set of strings over the alphabet {0,1,...,9} such that the final digit has not appeared before.
I have ...
1
vote
1
answer
80
views
CSS "escape" syntax diagram confusion
Have a look at the syntax diagram for the escape language:
I read the second set of transitions as follows:
The state transitioned to by the \ symbol can transition to the accepting state if the next ...
2
votes
1
answer
408
views
Non deterministic state machine using PyTransitions?
I am using pytransitions and have come across the need to have several states which are unrelated with others, and would make much sense to model using a non deterministic state machine, which is ...
1
vote
1
answer
158
views
Push Down Automata Using Fixed States
I've been asked to find the PDA for the language L over the alphabet {a,b,c,d} where L={(a^p)(b^2p)(c^r)(d^s)| p,r,s > 0 AND r=s}
I have solved it using 5 states but I must solve it using 6 states. ...
1
vote
2
answers
369
views
how would I build a generalized DFA for decimal Multiples of k?
Lets say I have a language like this: L_k:={w∈Σ∗: (w)10=i·k, i∈N}.
now using k as a parameter
I now want to define a DFA, that accepts L_{k}- and proof then that this DFA is valid. Important: k is a ...
1
vote
1
answer
1k
views
can a DFA have an arrow with empty string as input?
I've seen a picture of an automata represented as a DFA but it has arrows that has nothing on it!
What do these arrows mean in DFA? I mean are they different from epsilon (ε) , because we do not have ...
0
votes
1
answer
1k
views
A DFA for Kleene star operation
What would be the highest number of states a DFA would have for a language L*? Is it possible to define a worst-case scenario here?
0
votes
1
answer
607
views
Finding a grammar or a pushdown automaton that recognizes { a^i b^j b^i a^j | i,j >= 0 }
I am trying to find either a grammar or a pushdown automaton that recognizes the following language:
{ ai bj bi aj | i,j >= 0 }
Of all the examples that I have seen, I cannot wrap my head around ...