Theoretical Foundation of Computer Science.
Is this a regular language: a set consisting of strings x such that x is of prime length or x is of odd length. Prove your answer.
This is a language L consists of 2 other languages L1 : A set of strings X such that is X is of Prime length or L2 : Set of strings X such that X is of odd length.
L = L1 ? L2
For L to be regular both L1 and L2 should be regular.
A language is regualr if we can define a FINITE AUTOMATA for it.
L1 is not regular as we can't define a FINTITE AUTOMATA for it.
we can prove this by using PUMPING LEMMA.
The pumping lemma says that for any regular language L there
exists a constant p such that any word w in L with length at least
p can be split into three substrings,
w = xyz, where the middle portion y must not be empty, such that
the words xz, xyz, xyyz, xyyyz, … constructed by repeating y zero
or more times are still in L.
L1 = { X | K is length of X and K is a prime number}
RULE :
i.e w = word or input belongs to L1 / |w| >=n
w=xyz is in L1
For all i ? 0, the string xyiz is also in
L1
STEP 1 : Assume the given language is regular.
STEP2: As per pumping lemma , if the given language is regular, we can split the input w into 3 letters as xyz.
w = xyz
Length of xyz = K
|xyz| = K and |y|>=1 {As middle portion y must not be empty}
Now we will loop the middle portion y and check if it is belongs to the language of not.
|xyiz| = K , here i should >=0 as mentioned earlier.
So i value can also be K+1
i.e |xyK+1z| = |xyz|+|yK|
= K+ K(|y|) { As we already know length of xyz is K and y is repeating K times}
|xyiz| = K(1+|y|) {here lenght of y is not zero as per pumping lemma}
we are represening the value in mulples of some numbers , that means it is not a prime number.
As our state is not true, it is not REGULAR.
Even L2 is REGULAR as we can define a Finite automata but L1 is NOT REGULAR, L is NOT REGULAR.
Theoretical Foundation of Computer Science. Is this a regular language: a set consisting of strings x...
[Easy] Theoretical Computer Science Find a grammar for the following languages: (a) Set of binary numerals that represent odd natural numbers (b) Set of binary numerals that represent even natural numbers
Please help me with this... Give a regular grammar that generates the described language. The set of strings of odd length over {a, b} that contain exactly two b's.
Write down the regular expressions for the following set of strings over {a, b}: 1.Strings that contain no more than one occurrence of the string aa. 2.All strings containing aba: 3.All strings of odd length 4.A string in this language must have at least two a's. 5.All strings that begin with a, and have an even number of b Bonus - All strings with “a” at every odd position
The theoretical foundation of computer science. Q. Discuss size trade-offs between Turing machines and programs that compute the same function.
[Easy] Theoretical Computer Science Consider the grammar: Give a derivation for the string "aaaabbbbbb" and describe the language, i.e. general form of the strings generated by the grammar.
Construct a regular expression that recognizes the following language of strings over the alphabet {0 1}: The language consisting of the set of all bit strings that start with 00 or end with 101 (or both). Syntax The union is expressed as R|R, star as R*, plus as R+, concatenation as RR. Epsilon is not supported but you can write R? for the regex (R|epsilon).
Prove that the following language is not regular: { w1aw2 | w1,w2 ∈ {a,b}* and |w1| = |w2| } In other words, L consists of strings of odd length over the alphabet {a, b} which have a as its middle symbol. SHOW ALL WORK, THANKS!
Submit a DFA whose language is the set of strings over {a, b} of odd length in which every symbol is the same.
Exercise 4.1.1: Prove that the following are not regular languages a) (0"1n|n 2 1). This language, consisting of a string of 0's followed by an cqual-length string of 1's, is the language Loi we considered informally at the beginning of the scction. Here, you should apply the pumping lemma in the proof. b) The set of strings of balanced parentheses. These are the strings of char- acters "(" and " that can appear in a well-formed arithmetic expression *c) O"IO"...
Design a non-ambiguous grammar generating the language consisting of all binary strings, which contain an odd number of 0’s and an odd number of 1’s. Justify correctness of your construction.