698 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
3
votes
1
answer
74
views
Applying simplification rules to a DFA to derive a regular expression for it [closed]
I'm given this deterministic finite automaton (DFA):
I have to construct a regular expression for it. I do not understand one thing in the method described in my handbook.
First of all, we have to ...
0
votes
0
answers
37
views
I can't find the moore module in the automata-lib
I have a school project where I have to use the library automata-lib to code a moore machine. I have the 9.0.0 version of the library, just like all my colleagues, but mine doesn't seem to have the ....
5
votes
2
answers
200
views
3D Cubic Infinite Cellular Automata Challenge
I'm working on a challenge involving a 3D (cubic) infinite cellular automata defined as:
Initial State: We start with 8 cells positioned at the vertices of a cube and each cell is in one of 4 states {...
1
vote
0
answers
78
views
How do you parse a Synchronous Context Free Grammar?
I am trying to parse a grammar of this type:
g = """
S -> A{1} B{2}, S -> B{2} A{1}
A -> A{1} A{2}, A -> A{2} A{1}
B -> B{1} A{2}, B -> A{2} B{1}
A -> a, A -> e
...
-1
votes
1
answer
68
views
NFA with single transition per input and per state [closed]
I am new to automata. I am currently designing an NFA over the language {a, b} that should accept strings where the number of as is odd. I have designed an NFA for this, but I think it's kind of like, ...
1
vote
1
answer
127
views
Unmet Python Dependency Error While Installing Spot (w-Automata) on Ubuntu 24.04
I am trying to install Spot on an Ubuntu 24.04 virtual machine following the official instructions provided in the "Installing the Debian packages" section of the Spot website. The ...
1
vote
1
answer
215
views
Regex to DFA question, don't understand why it is this way
I've been dealing with problem 10 on Leetcode (Regular expression matching), where you are supposed to write a program that matches strings to a given regex.I wrote a solution in C that had passed 308 ...
0
votes
1
answer
57
views
Is this grammar LL(1)? Why so? If not, make it LL(1)
A -> Aac | Ab | Bb | a
B -> Ac | Ad | ε
Is this grammar LL(1)? Why so? If not, make it LL(1)
I need help solving this. I think it's not LL(1) because it has left recursion but I don't know ...
1
vote
1
answer
2k
views
Push Down Automata for the language L = { a^i b^j c^k | i, j, k >= 0 and j = i + 2k }
I drew PDA diagram for this language but it still does not work. Can some please help me? My PDA accepts 'bc' which it should not. I have no idea to control the b and c of the language. My scala code ...
0
votes
1
answer
462
views
Create a DFA that contains "11" or ends with "10"
I'm trying to construct a DFA (binary only) that contains "11" or ends with "10".
I tried to do the following:
$q2$ and $q3$ are accepting states
State
0
1
$q0$
$q0$
$q1$
$q1$
$q3$
...
0
votes
1
answer
278
views
Regex with even instances of ab and ba
I am trying to write a regex to match strings with even instances of ab and ba with only the alphabet of {a,b}.
I am trying to do so with only | and * operators. I think it has something to do with ...
2
votes
2
answers
179
views
How to detect programmatically if two Globs intersect or not in Node.js?
In below array, the first glob is a subset of the second one:
[
"HomePage/03-LocalDevelopmentBuild/public/**/*.@(js)",
"HomePage/03-LocalDevelopmentBuild/**/*.@(js)"
]
But how ...
0
votes
1
answer
420
views
How can I design a turing machine that recognises this language? 01^n01^n0
I keep on struggling with how to actually capture the number of 0's .
Do I use a different marker to capture 0 and 1? Or do I need to create new states that count the number of 0's? This doesn't seem ...
0
votes
1
answer
528
views
Find a finite automata that for the language L={0,1,2} | needs to include 1002 1,2 are odd and 0 is even
Find a finite automata that for the language L={0,1,2}
with the following criteria:
The word must contain "1002".
The number of occurrences of 1 must be odd
The number of occurrences of 2 ...
0
votes
1
answer
362
views
Need clarification on pumping lemma for context free languages
I am doing a problem where I am applying pumping lemma to the CFL L = {a^nb^nc^n : n >= 0}. Here is the start of a proof I was looking at:
Assume L is a CFL, so there exists a pumping length p for ...